Решение проблемы Leetcode 1221: Разделить строку в Balance Strings

В этой задаче Leetcode нас просят разбить строку, содержащую одинаковое количество «L» и «R» (и только эти символы), на максимальное количество подстрок с этим свойством, а затем вернуть максимальное количество разбиений, которые осуществимо.

Например, RLRRLLLRLR можно разделить на RL, RRLL, LR и LR, и тогда мы должны вернуть 4.

Идея состоит в том, чтобы найти минимальную подстроку Sleft из S так, чтобы S = Sleft + Sright с Sleft были сбалансированы. Прямым следствием является то, что правая сторона S уравновешена, и мы можем продолжить поиск дополнительных расщеплений в Sright.

На практике это означает, что нам нужно только подсчитать количество встреченных L и R и добавить 1 к количеству разбиений каждый раз, когда эти числа равны при повторении через S.

Решение:

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;
    }
}