Задача: 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⃣Использование скользящего окна:
Используем метод двух указателей (скользящее окно) для нахождения минимальной подстроки, которую можно заменить, чтобы строка стала сбалансированной.
Начнем с окна, которое захватывает всю строку, и будем постепенно уменьшать его, проверяя при каждом шаге, становится ли строка сбалансированной.

😎 Решение:

var balancedString = function(s) {
    const n = s.length;
    const count = new Map();
    for (const c of s) {
        count.set(c, (count.get(c) || 0) + 1);
    }
    const target = n / 4;

    const isBalanced = () => {
        return 'QWER'.split('').every(c => (count.get(c) || 0) <= target);
    };

    if (isBalanced()) return 0;

    let minLength = n;
    let left = 0;

    for (let right = 0; right < n; right++) {
        count.set(s[right], count.get(s[right]) - 1);
        while (isBalanced()) {
            minLength = Math.min(minLength, right - left + 1);
            count.set(s[left], (count.get(s[left]) || 0) + 1);
            left++;
        }
    }

    return minLength;
};

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