Split a String in Balanced Strings — Problem & Solution
Split a String in Balanced Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Split a String in Balanced Strings is an easy coding problem on strings, greedy and counting, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Strings, Greedy, Counting
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A string is balanced when it contains an equal number of 'L' and 'R' characters.
Given a balanced string s, split it into the maximum number of balanced substrings and return that count.
Example 1
Input: s = "RLRRLLRLRL"
Output: 4
Explanation: The pieces are "RL", "RRLL", "RL" and "RL".
Example 2
Input: s = "RLRRRLLRLL"
Output: 2
Example 3
Input: s = "LLLLRRRR"
Output: 1
Constraints
2 <= s.length <= 40s[i] is 'L' or 'R'.s is balanced.
Hints for Split a String in Balanced Strings
Hint 1
Track a running balance: +1 for
R, -1 forL.Hint 2
Every time the balance returns to zero, you have completed a balanced piece — cut there.
Hint 3
Cutting at the earliest opportunity is what maximises the count.
How to solve Split a String in Balanced Strings
Keep a running balance (+1 for R, -1 for L) and cut every time it returns to zero.
Approach
- Set
balance = count = 0. - For each character, adjust
balance; when it hits 0, incrementcount. - Return
count.
Why it works
Each return to zero closes a balanced piece, and cutting at the earliest opportunity never prevents later cuts — any balanced string splits into the pieces between successive zero crossings, which is the maximum.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Greedy is exact here because the whole string is guaranteed balanced.
Reference solution
Python
def balancedStringSplit(s: str) -> int:
balance = count = 0
for ch in s:
balance += 1 if ch == "R" else -1
if balance == 0:
count += 1
return countJava
public static int balancedStringSplit(String s) {
int balance = 0, count = 0;
for (int i = 0; i < s.length(); i++) {
balance += s.charAt(i) == 'R' ? 1 : -1;
if (balance == 0) count++;
}
return count;
}C++
int balancedStringSplit(string s) {
int balance = 0, count = 0;
for (char c : s) {
balance += c == 'R' ? 1 : -1;
if (balance == 0) count++;
}
return count;
}JavaScript
var balancedStringSplit = function(s) {
let balance = 0, count = 0;
for (let i = 0; i < s.length; i++) {
balance += s[i] === "R" ? 1 : -1;
if (balance === 0) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms