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 themaximum number of balanced strings you can obtain.
Examples# Example 1# 1
2
3
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# 1
2
3
4
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 2 nd and 5 th substrings are not balanced.
Example 3# 1
2
3
Input: s = "LLLLRRRR"
Output: 1
Explanation: s can be split into "LLLLRRRR" .
Constraints# 2 <= s.length <= 1000
s[i]
is either 'L'
or 'R'
.s
is a balanced string.Solution# Method 1 – Greedy Counting# Intuition# Track the difference between the number of ‘L’ and ‘R’ characters as you scan the string. Every time the counts are equal, a balanced substring is found.
Approach# Initialize a counter to zero and a result variable to zero. Iterate through the string:Increment the counter for ‘L’, decrement for ‘R’. When the counter reaches zero, increment the result (a balanced substring is found). Return the result. Code#
Cpp
Go
Java
Kotlin
Python
Rust
Typescript
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public :
int balancedStringSplit(string s) {
int cnt = 0 , ans = 0 ;
for (char c : s) {
cnt += (c == 'L' ? 1 : - 1 );
if (cnt == 0 ) ++ ans;
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func balancedStringSplit (s string ) int {
cnt , ans := 0 , 0
for _ , c := range s {
if c == 'L' {
cnt ++
} else {
cnt --
}
if cnt == 0 {
ans ++
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
class Solution {
public int balancedStringSplit (String s) {
int cnt = 0, ans = 0;
for (char c : s.toCharArray ()) {
cnt += (c == 'L' ? 1 : - 1);
if (cnt == 0) ++ ans;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
class Solution {
fun balancedStringSplit (s: String): Int {
var cnt = 0
var ans = 0
for (c in s) {
cnt += if (c == 'L' ) 1 else -1
if (cnt == 0 ) ans++
}
return ans
}
}
1
2
3
4
5
6
7
def balancedStringSplit (s: str) -> int:
cnt = ans = 0
for c in s:
cnt += 1 if c == 'L' else - 1
if cnt == 0 :
ans += 1
return ans
1
2
3
4
5
6
7
8
9
10
impl Solution {
pub fn balanced_string_split (s: String) -> i32 {
let (mut cnt, mut ans) = (0 , 0 );
for c in s.chars() {
cnt += if c == 'L' { 1 } else { - 1 };
if cnt == 0 { ans += 1 ; }
}
ans
}
}
1
2
3
4
5
6
7
8
9
10
class Solution {
balancedStringSplit (s : string ): number {
let cnt = 0 , ans = 0 ;
for (const c of s ) {
cnt += c === 'L' ? 1 : - 1 ;
if (cnt === 0 ) ans ++ ;
}
return ans ;
}
}
Complexity# ⏰ Time complexity: O(n)
– Single pass through the string. 🧺 Space complexity: O(1)
– Only counters are used.