Abstract / Summary

We need to determine if we can split a given string into pairs of identical characters.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 66% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Sliding Window

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of finding the minimum number of swaps required to group all 1s together in a circular array. It treats the array as circular by virtually extending it, then uses a sliding window of length equal to the total count of 1s to evaluate every possible grouping. The algorithm returns the smallest number of 0s that must be swapped into the window, which directly corresponds to the minimal swap count.

Key Steps

The solution proceeds through a sequence of well-defined operations.

The first operation determines how many 1s exist in the input.

ones = nums.count(1)

If the count is zero or one, no rearrangement can improve the situation, so the function returns immediately.

if ones <= 1:
    return 0

Next, the algorithm evaluates the initial window that starts at index 0 and spans ones elements. It counts how many 1s already reside in that window.

have = nums[:ones].count(1)
best = ones - have

The variable best holds the current best (minimum) number of swaps required, initialized with the swaps needed for the first window.

To handle the circular nature of the problem, the original list is concatenated with its leading segment of length ones. This creates a temporary array that contains every possible window without needing modular arithmetic.

twice = nums + nums[:ones]

A sliding window then traverses the extended array. For each new position, the algorithm updates the count of 1s inside the window by adding the element that enters on the right and subtracting the element that leaves on the left.

for right in range(ones, len(twice)):
    have += twice[right]
    have -= twice[right - ones]
    best = min(best, ones - have)
    if best == 0:
        break

During each iteration, best is refreshed with the smaller of its current value and the swaps needed for the current window (ones - have). An early-exit condition stops the loop as soon as a window requiring zero swaps is found, because no better result can exist.

Finally, the function returns the smallest swap count discovered.

return best

Edge Cases

The code explicitly handles the situation where the array contains at most a single 1. In such cases the grouping is already optimal, and the function returns 0 without further processing.

When the array consists entirely of 1s, the initial window already contains all 1s, so have equals ones and best becomes 0. The early-exit clause triggers immediately, avoiding unnecessary iterations.

The duplication step (twice = nums + nums[:ones]) guarantees that windows crossing the original array’s end are represented correctly. For example, with nums = [0,1,0,1] and ones = 2, the extended array becomes [0,1,0,1,0,1]. Sliding windows of length 2 over this sequence cover the wrap-around windows [1,0] and [0,1] that would otherwise require modular index calculations.

If the input list is empty, ones evaluates to 0, satisfying the early return condition and yielding 0 swaps.

Performance Optimizations

The implementation minimizes redundant work in several ways. Counting the total number of 1s (nums.count(1)) and the initial window’s 1s (nums[:ones].count(1)) are performed only once, avoiding repeated scans.

The sliding window updates the count of 1s in constant time per step by adjusting for the element that leaves and the element that enters. This eliminates the need to recount the entire window on each shift.

Creating the extended array (twice) only once allows the loop to use simple index arithmetic without modulo operations, which reduces overhead in tight loops.

The early-exit condition (if best == 0: break) stops the algorithm as soon as an optimal window is found, preventing the traversal of the remaining positions when further improvement is impossible.

Overall, the algorithm runs in linear time relative to the length of the input list, with a modest amount of additional memory used for the duplicated segment.

Imagine a long train made of many colorful toy cars. Some of the cars are red and some are blue. The goal is to get all the red cars to sit right next to each other in a row, even if the train connects at the ends like a circle.

The code starts by counting how many red cars are in the whole train. If there is only one red car, it is already in a perfect group, so no work is needed.

Next, the code looks at a small section of the train that is the same size as the total number of red cars. It counts how many red cars are hiding in that little section. If this section is not full of red cars, some blue cars are taking up space. The number of blue cars in that spot tells how many swaps are needed to put red cars there instead.

To see every possible group, the code slides this tiny section along the train, one car at a time. Every time the section moves forward, it forgets the car it just left behind and welcomes a new car from the front. The train is even doubled at the end so it can easily wrap back around to the beginning like a giant loop.

During this slide, the code keeps track of the best spot found so far. It wants the spot that needs the fewest swaps to fill up with red cars. Once it finds a spot that is already completely full of red cars, it stops looking because it knows it cannot do better than zero.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java				TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python	JS	Java	C#	Go	Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	fsq	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM					C#
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality