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 2nd and 5th 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

  1. Initialize a counter to zero and a result variable to zero.
  2. 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).
  3. Return the result.

Code

 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.