Условие

Дана строка s, содержащая только символы 'L' и 'R'. Строка называется сбалансированной, если количество 'L' равно количеству 'R'. Нужно определить максимальное количество сбалансированных подстрок, на которые можно разделить s.

Примеры

Input: "RLRRLLRLRL” Output: 4 Explanation: s можно разделить на "RL", "RRLL", "RL", "RL", каждая подстрока содержит одинаковое количество 'L' и 'R'.

Input: "RLLLLRRRLR” Output: 3 Explanation: s можно разделить на "RL", "RRRLLRLL", каждая подстрока содержит одинаковое количество 'L' и 'R'. Обрати внимание, что s нельзя разделить на "RL", "RR", "RL", "LR", "LL", потому что 2-я и 5-я подстроки несбалансированы.

Input: "LLLLRRRR” Output: 1 Explanation: s можно разделить на "LLLLRRRR".

Решение

fun balancedStringSplit(s: String): Int {
    var count = 0
    var balance = 0

    for (char in s) {
        balance += if (char == 'L') 1 else -1
        if (balance == 0) count++
    }
    return count
}

Временная сложность

O(n), где n — длина строки s.

Пространственная сложность

O(1), так как используются только счётчики.