Задача: 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 {
public:
    int balancedString(string s) {
        int n = s.size();
        unordered_map<char, int> count;
        for (char c : s) count[c]++;
        int target = n / 4;

        auto is_balanced = [&]() {
            return count['Q'] <= target && count['W'] <= target && count['E'] <= target && count['R'] <= target;
        };

        if (is_balanced()) return 0;

        int min_length = n;
        int left = 0;

        for (int right = 0; right < n; ++right) {
            count[s[right]]--;
            while (is_balanced()) {
                min_length = min(min_length, right - left + 1);
                count[s[left]]++;
                left++;
            }
        }

        return min_length;
    }
};

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