How to Split a String in Balanced Strings?

Balanced strings are those who have equal quantity of ‘L’ and ‘R’ characters. Given a balanced string s split it in the maximum amount of balanced strings. Return the maximum amount of splitted balanced strings.

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 = “RLLLLRRRLR”
Output: 3
Explanation: s can be split into “RL”, “LLLRRR”, “LR”, each substring contains same number of ‘L’ and ‘R’.

Example 3:
Input: s = “LLLLRRRR”
Output: 1
Explanation: s can be split into “LLLLRRRR”.

Constraints:
1 <= s.length <= 1000
s[i] = ‘L’ or ‘R’

Hints:
Loop from left to right maintaining a balance variable when it gets an L increase it by one otherwise decrease it by one.
Whenever the balance variable reaches zero then we increase the answer by one.

Balancing Parentheses Algorithm

This is quite similar to the Parentheses algorithms that we can use a variable to keep tracking the balance i.e. when we meet a left Parentheses, we increment the balance or decrement it otherwise. If the balance becomes zero, we increment the split count.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int balancedStringSplit(string s) {
        int bal = 0, ans = 0;
        for (const auto &n: s) {
            if (n == 'L') {
                bal ++;
            } else {
                bal --;
            }
            if (bal == 0) {
                ans ++;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int balancedStringSplit(string s) {
        int bal = 0, ans = 0;
        for (const auto &n: s) {
            if (n == 'L') {
                bal ++;
            } else {
                bal --;
            }
            if (bal == 0) {
                ans ++;
            }
        }
        return ans;
    }
};

O(N) time where N is the size of the input string. O(1) constant space is required.

–EOF (The Ultimate Computing & Technology Blog) —