Split a String in Balanced Strings - Solution & Explanation
Problem Statement
Balanced strings are those that have an equal quantity of 'L' and 'R' characters.
Given a balanced string s, split it into some number of substrings such that:
- Each substring is balanced.
Return the maximum number of balanced strings you can obtain.
Example 1:
Input: s = "RLRRLLRLRL" Output: 4 Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.
Example 2:
Input: s = "RLRRRLLRLL" Output: 2 Explanation: s can be split into "RL", "RRRLLRLL", each substring contains same number of 'L' and 'R'. Note that s cannot be split into "RL", "RR", "RL", "LR", "LL", because the 2nd and 5th substrings are not balanced.
Example 3:
Input: s = "LLLLRRRR" Output: 1 Explanation: s can be split into "LLLLRRRR".
Constraints:
2 <= s.length <= 1000s[i]is either'L'or'R'.sis a balanced string.
Approach Overview
Problem Overview: You receive a string consisting only of characters L and R. A substring is balanced when the number of L and R characters are equal. The goal is to split the string into the maximum number of balanced substrings.
Approach 1: Greedy Approach Using Counter (Time: O(n), Space: O(1))
This problem fits naturally with a greedy strategy. Traverse the string once while maintaining a single counter. Increment the counter when you see L and decrement it when you see R (or vice versa). Whenever the counter returns to zero, the current segment contains equal numbers of both characters, meaning a balanced substring has been found. Increment the result and continue scanning the rest of the string.
The key insight: the earliest point where the running difference between L and R becomes zero forms a valid balanced substring. Splitting immediately maximizes the number of possible splits later. Since the algorithm processes each character exactly once and stores only a few integers, the time complexity is O(n) and the space complexity is O(1). This approach relies on simple counting logic and works efficiently even for large strings.
Approach 2: Two Counter Method (Time: O(n), Space: O(1))
Another way to implement the same idea is by explicitly maintaining two counters: one for L and one for R. Iterate through the string and update the appropriate counter for each character. After each update, compare the two counters. When they become equal, a balanced substring is complete. Increase the split count and continue scanning the remaining characters.
This approach is slightly more verbose but often easier to reason about for beginners because it directly tracks both character counts. The algorithm still performs a single pass through the string, giving O(n) time complexity with O(1) auxiliary space. The trade‑off is simply maintaining two integers instead of one difference counter.
Recommended for interviews: Interviewers typically expect the greedy counter approach. It shows you recognize that balanced segments can be finalized the moment the running difference reaches zero. The two‑counter method demonstrates the same concept but with more explicit state tracking. Showing both approaches communicates a clear understanding of the underlying counting principle and why the greedy split guarantees the maximum number of balanced substrings.
Approach 1: Greedy Approach Using Counter
This approach uses a single pass through the string while maintaining a balance counter. Start with a balance of 0 and traverse the string. Increment the balance by 1 for an 'R' and decrement it by 1 for an 'L'. Every time the balance equals zero, it means we have found a balanced substring. Increase the count of balanced substrings at these points.
This C program reads a string and splits it into balanced strings by iterating and using a balance counter. 'R' increments the balance, while 'L' decrements it. Upon reaching a balance of zero, a balanced string is counted.
Complexity
Time Complexity: O(n), where n is the length of the string. The function makes a single pass through the string.
Space Complexity: O(1), as only a few variables are used regardless of the input size.
Approach 2: Two Counter Method
This approach involves using two separate counters specifically counting 'L' and 'R'. As we traverse the string, increment the respective counter for 'L' and 'R'. Whenever the two counters are equal, it indicates a balanced substring.
This C solution uses separate counters for 'L' and 'R', checking for equality to indicate balanced substrings. On equal counts, it resets the counters.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Greedy
We use a variable l to maintain the current balance of the string, i.e., the value of l is the number of 'L's minus the number of 'R's in the current string. When the value of l is 0, we have found a balanced string.
We traverse the string s. When we traverse to the i-th character, if s[i] = L, then the value of l is increased by 1, otherwise, the value of l is decreased by 1. When the value of l is 0, we increase the answer by 1.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the string s.
Code
Python
Java
C++
Go
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach Using Counter | Time Complexity: O(n), where n is the length of the string. The function makes a single pass through the string. |
| Two Counter Method | Time Complexity: O(n) |
| Greedy | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Approach Using Counter | O(n) | O(1) | Best general solution. Minimal state and a single pass through the string. |
| Two Counter Method | O(n) | O(1) | Useful when you want explicit counts of L and R for clarity or debugging. |
Video Solution
Split a String in Balanced Strings • Kevin Naughton Jr. • 29,833 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Split a String in Balanced Strings easy or hard?
Split a String in Balanced Strings Python/Java solution
How to solve Split a String in Balanced Strings in O(n)?
What is the best approach for Split a String in Balanced Strings?
Is Split a String in Balanced Strings asked at Google/Amazon/Meta?
What data structure is used in Split a String in Balanced Strings?
What is the time complexity of Split a String in Balanced Strings?
Ready to solve this problem?
Practice Split a String in Balanced Strings with our built-in code editor and test cases.
Practice on FleetCode