Solution to Leetcode problem 1221: Split a string in Balances Strings

In this Leetcode problem, we are asked to split a string containing the same number of ‘L’ and ‘R’ (and only these characters), into the maximum number of substring with this property, and then return the maximum number of split that can be done.

Problem statement

For instance RLRRLLLRLR can be split in RL, RRLL, LR, and LR, and we should then return 4.

The idea is to find the minimum substring Sleft of S so that S = Sleft + Sright with Sleft balanced. An immediate consequence is that S right is balanced, and we can then keep searching for more splits in Sright.

Practically, this means we only need to count the number of L and R encountered, and add 1 to the number of splits each time these numbers are equal when iterating through S.

Solution:

class Solution {
    public int balancedStringSplit(String s) {
        int res = 0;
        int counter = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'L') {
                counter++;
            } else {
                counter--;
            }
            if (counter == 0) {
                res++;
            }
        }
        return res;
    }
}