Задача: 1234. Replace the Substring for Balanced String
Сложность: medium

Вам дана строка s длины n, содержащая только четыре вида символов: 'Q', 'W', 'E' и 'R'. Строка считается сбалансированной, если каждый из ее символов встречается n / 4 раз, где n - длина строки. Верните минимальную длину подстроки, которую можно заменить любой другой строкой той же длины, чтобы сделать s сбалансированной. Если s уже сбалансирована, верните 0.

Пример:

Input: s = "QWER"
Output: 0

👨‍💻 Алгоритм:

1⃣Проверка баланса:
Сначала проверим, сбалансирована ли строка s. Если да, то возвращаем 0.

2⃣Подсчет частоты символов:
Подсчитаем количество каждого символа в строке s.

3⃣Использование скользящего окна:
Используем метод двух указателей (скользящее окно) для нахождения минимальной подстроки, которую можно заменить, чтобы строка стала сбалансированной.
Начнем с окна, которое захватывает всю строку, и будем постепенно уменьшать его, проверяя при каждом шаге, становится ли строка сбалансированной.

😎 Решение:

class Solution {
    func balancedString(_ s: String) -> Int {
        var count = [Character: Int]()
        for char in s { count[char, default: 0] += 1 }
        let target = s.count / 4

        func isBalanced() -> Bool {
            for char in "QWER" {
                if count[char, default: 0] > target {
                    return false
                }
            }
            return true
        }

        if isBalanced() { return 0 }

        let chars = Array(s)
        var minLength = s.count
        var left = 0

        for right in 0..<s.count {
            count[chars[right]]! -= 1
            while isBalanced() {
                minLength = min(minLength, right - left + 1)
                count[chars[left]]! += 1
                left += 1
            }
        }

        return minLength
    }
}

Ставь 👍 и забирай 📚 Базу знаний