Skip to content

1221. Split a String in Balanced Strings

SourceWeekly Contest 158 Q1DifficultyEasyRating1219

Description

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 <= 1000
  • s[i] is either 'L' or 'R'.
  • s is a balanced string.

Solutions

Solution 1: Greedy

Thinking

The whole string is balanced; we want as many balanced pieces as possible. Cutting as soon as a prefix balances never blocks later cuts: each cut adds one to the answer and leaves a balanced suffix.

A counter tracks the \(L\)/\(R\) difference and hits zero on each balanced prefix. We increment the answer and continue. The greedy cuts stay in lockstep with the counter in one linear pass.

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\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def balancedStringSplit(self, s: str) -> int:
        ans = l = 0
        for c in s:
            if c == 'L':
                l += 1
            else:
                l -= 1
            if l == 0:
                ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int balancedStringSplit(String s) {
        int ans = 0, l = 0;
        for (char c : s.toCharArray()) {
            if (c == 'L') {
                ++l;
            } else {
                --l;
            }
            if (l == 0) {
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int balancedStringSplit(string s) {
        int ans = 0, l = 0;
        for (char c : s) {
            if (c == 'L')
                ++l;
            else
                --l;
            if (l == 0) ++ans;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} s
 * @return {number}
 */
var balancedStringSplit = function (s) {
    let ans = 0;
    let l = 0;
    for (let c of s) {
        if (c == 'L') {
            ++l;
        } else {
            --l;
        }
        if (l == 0) {
            ++ans;
        }
    }
    return ans;
};

Comments