Abstract / Summary

Split a string into as many balanced groups as possible where each group has the same number of x and y 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 88% (400k+ submissions).

Typical patterns to solve this problem:

• Counting
• Greedy
• String

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 defines a method that counts how many substrings of the input can be partitioned such that each substring contains an equal number of the characters L and R. The algorithm walks through the string once, maintaining a running balance between the two characters. Whenever the balance returns to zero, a balanced segment has been completed and the result counter is increased. The final count is returned.

Key Steps

Initialization

result  = 0
balance = 0

Two integer variables are created before the iteration begins. result stores the number of balanced substrings discovered so far, while balance tracks the net difference between L and R characters encountered up to the current position.

Single-Pass Traversal

for c in s:
    if c == "L":
        balance += 1
    else:
        balance -= 1
``

The loop processes each character in the input string exactly once. When the character is **L**, the balance is incremented; for any other character (implicitly **R** in the problem domain) the balance is decremented. This simple conditional update keeps the balance reflecting the surplus of **L** over **R** seen so far.

## Detecting a Balanced Segment

```python
if balance == 0:
    result += 1

Immediately after updating the balance, the code checks whether the net difference has returned to zero. A zero balance indicates that the characters seen since the previous zero balance (or the start of the string) form a substring with equal numbers of L and R. At that moment the result counter is incremented, marking the completion of one balanced segment.

Returning the Count

return result

After the loop finishes, the accumulated count of balanced substrings is returned to the caller.

Edge Cases Handled

When the input string is empty, the loop body never executes, leaving both balance and result at zero. The method correctly returns zero, indicating that no balanced substrings exist.

If the string consists entirely of L characters, the balance will never return to zero after the initial state, so result remains zero. This reflects the fact that no substring can be balanced without any R characters.

Conversely, a string that alternates L and R (e.g., "LRLR") causes the balance to hit zero after each pair, resulting in a count equal to the number of pairs. The algorithm naturally captures this pattern without additional logic.

When the string ends with a non-zero balance, the final incomplete segment is ignored because the condition balance == 0 is never satisfied for that trailing portion. This behavior aligns with the requirement to count only fully balanced substrings.

Performance Optimizations

The solution achieves optimal efficiency by performing a single linear scan of the input. No auxiliary data structures such as stacks, dictionaries, or lists are allocated; only two integer variables are used throughout execution. This constant-space approach minimizes memory overhead regardless of input length.

By updating the result counter immediately when the balance reaches zero, the algorithm avoids a second pass or any backtracking. The early detection of a balanced segment allows the method to progress directly to the next potential segment, ensuring that each character contributes to exactly one balance computation and at most one result increment.

Overall, the design leverages straightforward arithmetic and conditional checks to deliver a fast, memory-light solution for counting balanced substrings.

Imagine you have a long row of building blocks, and each block is either a letter L or a letter R. This code acts like a little helper that walks along the row of blocks one by one to count how many perfect groups you can make.

The helper keeps track of a score called balance. Every time the helper sees an L, it adds one to the score. Every time it sees an R, it takes one away from the score. Think of this like balancing a scale. Whenever the score hits zero, it means the number of L blocks and R blocks are exactly the same, making one balanced group.

When the scale hits zero, the helper marks down one point for that group and keeps moving down the line to see if it can find another balanced group. It continues doing this until it reaches the very end of all the blocks.

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++
	leetcode.ca	C++	Python	JS	Java				Go
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai				Java
	DimitrisJim						C
	everthis			JS
	fartem							Ruby
	fsq	C++
	halfrost								Go
	JoshCrozier			JS
	keineahnung2345	C++
	Krazune						C
	lkwq007		Python
	suxrobGM					C#
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++
leetcode.ca	C++, Go, Java, JavaScript, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C
lkwq007	Python
suxrobGM	C#
varunu28	Java
YuriSpiridonov	Python

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