Условие

Дана бинарная строка s. Нужно вернуть количество непустых подстрок, содержащих равное количество последовательных 0 и 1, и в которых все 0 и 1 группируются вместе.

Примеры

Input: s = "00110011” Output: 6 Explanation: Шесть подстрок удовлетворяют условиям: "0011", "01", "1100", "10", "0011", "01".

Input: s = "10101” Output: 4 Explanation: Четыре подстроки удовлетворяют условиям: "10", "01", "10", "01".

Решение

fun countBinarySubstrings(s: String): Int {
    var prevGroupLength = 0 // Длина предыдущей группы одинаковых символов
    var currGroupLength = 1 // Длина текущей группы одинаковых символов
    var count = 0 // Количество подходящих подстрок

    for (i in 1 until s.length) {
        if (s[i] == s[i - 1]) {
            // Увеличиваем текущую длину, если символ совпадает с предыдущим
            currGroupLength++
        } else {
            // Обновляем счётчик, когда группы меняются
            count += minOf(prevGroupLength, currGroupLength)
            prevGroupLength = currGroupLength
            currGroupLength = 1
        }
    }
    // Добавляем последний набор групп
    count += minOf(prevGroupLength, currGroupLength)
    return count
}

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

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

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

O(1), так как используется фиксированное количество переменных.