Split a String in Balanced Strings solution and explanation
Google
9 more videos on this problem
Split a String in Balanced StringsKevin Naughton Jr. · 7:05 · 29K views
Split a String in Balanced Strings | Easiest Solution | LeetCode 1221 | Interview QuestionClashing Coder · 11:26 · 4K views
Leetcode #1221 - Split a STRING in Balanced StringsAlgoSTEM · 3:24 · 3K views
Leetcode | 1221. Split a String in Balanced Strings | Easy | Java SolutionDeveloper Docs · 3:51 · 1K views
LeetCode: 1221. Split a String in Balanced Strings | Python EasyNaveen V · 5:45 · 625 views
LeetCode 1221 : Split a String in Balanced Strings || EASY || C++ || JAVA || Detailed SolutionCodeGPT · 8:19 · 554 views
leetcode - 1221 Split a String in Balanced Strings JavaScript SolutionlitCode · 6:34 · 513 views
Leetcode Solution - 1221 Split a String in Balanced StringsJohn Leonardo · 3:08 · 458 views
How to Solve "1221 Split a String in Balanced Strings" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 5:50 · 200 views
LEETCODE: Split a String in Balanced StringsNicholas Facciola · 6:27 · 177 views
The problem
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.
def balancedStringSplit(s: str) -> int:
balance = 0
max_balanced = 0
for char in s:
balance += 1 if char == 'R' else -1
if balance == 0:
max_balanced += 1
return max_balanced
print(balancedStringSplit("RLRRLLRLRL"))public class Solution {
public int balancedStringSplit(String s) {
int balance = 0, max_balanced = 0;
for (char c : s.toCharArray()) {
balance += (c == 'R') ? 1 : -1;
if (balance == 0) {
max_balanced++;
}
}
return max_balanced;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.balancedStringSplit("RLRRLLRLRL"));
}
}#include <iostream>
#include <string>
using namespace std;
int balancedStringSplit(string s) {
int balance = 0, max_balanced = 0;
for (char c : s) {
balance += (c == 'R') ? 1 : -1;
if (balance == 0) {
max_balanced++;
}
}
return max_balanced;
}
int main() {
cout << balancedStringSplit("RLRRLLRLRL") << endl;
return 0;
}function balancedStringSplit(s) {
let balance = 0;
let max_balanced = 0;
for(let char of s) {
balance += (char === 'R') ? 1 : -1;
if(balance === 0) {
max_balanced++;
}
}
return max_balanced;
}
console.log(balancedStringSplit("RLRRLLRLRL"));#include <stdio.h>
int balancedStringSplit(char * s) {
int balance = 0, max_balanced = 0;
for (int i = 0; s[i] != '\0'; i++) {
balance += (s[i] == 'R') ? 1 : -1;
if (balance == 0) {
max_balanced++;
}
}
return max_balanced;
}
int main() {
char s[] = "RLRRLLRLRL";
printf("%d\n", balancedStringSplit(s));
return 0;
}using System;
public class Solution {
public int BalancedStringSplit(string s) {
int balance = 0, max_balanced = 0;
foreach (char c in s) {
balance += (c == 'R') ? 1 : -1;
if (balance == 0)
max_balanced++;
}
return max_balanced;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.BalancedStringSplit("RLRRLLRLRL"));
}
}In this Python function, the string is traversed to keep a counter of the balance of 'R' and 'L'. Each time the counter is zero, it indicates a balanced substring.
Time Complexity: O(n)
Space Complexity: O(1)
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.
def balancedStringSplit(s: str) -> int:
r_count, l_count = 0, 0
max_balanced = 0
for char in s:
if char == 'R':
r_count += 1
else:
l_count += 1
if r_count == l_count:
max_balanced += 1
r_count, l_count = 0, 0
return max_balanced
print(balancedStringSplit("RLRRLLRLRL"))public class Solution {
public int balancedStringSplit(String s) {
int r_count = 0, l_count = 0, max_balanced = 0;
for (char c : s.toCharArray()) {
if (c == 'R') r_count++;
else l_count++;
if (r_count == l_count) {
max_balanced++;
r_count = l_count = 0;
}
}
return max_balanced;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.balancedStringSplit("RLRRLLRLRL"));
}
}#include <iostream>
#include <string>
using namespace std;
int balancedStringSplit(string s) {
int r_counter = 0, l_counter = 0, max_balanced = 0;
for (char c : s) {
r_counter += (c == 'R');
l_counter += (c == 'L');
if (r_counter == l_counter) {
max_balanced++;
r_counter = l_counter = 0;
}
}
return max_balanced;
}
int main() {
cout << balancedStringSplit("RLRRLLRLRL") << endl;
return 0;
}function balancedStringSplit(s) {
let r_counter = 0, l_counter = 0, max_balanced = 0;
for(let char of s) {
if(char === 'R') r_counter++;
else l_counter++;
if(r_counter === l_counter) {
max_balanced++;
r_counter = l_counter = 0;
}
}
return max_balanced;
}
console.log(balancedStringSplit("RLRRLLRLRL"));#include <stdio.h>
int balancedStringSplit(char * s) {
int r_counter = 0, l_counter = 0, max_balanced = 0;
for (int i = 0; s[i] != '\0'; i++) {
r_counter += (s[i] == 'R');
l_counter += (s[i] == 'L');
if (r_counter == l_counter) {
max_balanced++;
r_counter = l_counter = 0;
}
}
return max_balanced;
}
int main() {
char s[] = "RLRRLLRLRL";
printf("%d\n", balancedStringSplit(s));
return 0;
}using System;
public class Solution {
public int BalancedStringSplit(string s) {
int r_counter = 0, l_counter = 0, max_balanced = 0;
foreach (char c in s) {
if (c == 'R') r_counter++;
else l_counter++;
if (r_counter == l_counter) {
max_balanced++;
r_counter = l_counter = 0;
}
}
return max_balanced;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.BalancedStringSplit("RLRRLLRLRL"));
}
}In Python, separate counters are used to track 'R' and 'L'. When the counts are equal, it denotes a balanced substring, prompting counter resets.
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.
func balancedStringSplit(s string) int {
ans, l := 0, 0
for _, c := range s {
if c == 'L' {
l++
} else {
l--
}
if l == 0 {
ans++
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach Using Counter | Time Complexity: O(n) |
| Two Counter Method | Time Complexity: O(n) |
| Greedy | – |
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. |
Frequently asked questions
Is Split a String in Balanced Strings easy or hard?
Split a String in Balanced Strings is classified as an Easy problem on LeetCode with a high acceptance rate around 87%. The challenge focuses on recognizing a greedy counting pattern and implementing a single-pass solution.
Split a String in Balanced Strings Python/Java solution
In Python or Java, the solution typically uses a loop and an integer counter. Increase the counter for 'L', decrease for 'R', and increment the answer whenever the counter becomes zero. The logic remains identical across languages such as Python, Java, C++, and JavaScript.
How to solve Split a String in Balanced Strings in O(n)?
Iterate through the string while tracking the difference between the number of 'L' and 'R' characters. Increase the counter for 'L' and decrease it for 'R'. When the counter reaches zero, you have a balanced substring, so increment the result and continue scanning. This single-pass greedy approach guarantees O(n) time.
What is the best approach for Split a String in Balanced Strings?
The greedy counter approach is the most efficient solution. Traverse the string once and maintain a running counter that increments for 'L' and decrements for 'R'. Whenever the counter becomes zero, a balanced substring is formed. This method runs in O(n) time with O(1) extra space.
Is Split a String in Balanced Strings asked at Google/Amazon/Meta?
Variants of counting and greedy string problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem is commonly associated with LeetCode practice, the underlying pattern—tracking balance using counters—is widely tested in coding interviews.
What data structure is used in Split a String in Balanced Strings?
The solution mainly relies on simple integer counters rather than complex data structures. A single difference counter or two separate counters track the number of 'L' and 'R' characters while iterating through the string.
What is the time complexity of Split a String in Balanced Strings?
The optimal solution runs in O(n) time because the algorithm scans the string exactly once. Each character updates a counter or two counters. Space complexity is O(1) since only a few integer variables are required regardless of input size.