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

😎 Решение:

public class Solution {
    public int BalancedString(string s) {
        int n = s.Length;
        var count = new Dictionary<char, int>();
        foreach (char c in s) {
            if (count.ContainsKey(c)) count[c]++;
            else count[c] = 1;
        }
        int target = n / 4;

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

        if (IsBalanced()) return 0;

        int minLength = n;
        int left = 0;

        for (int right = 0; right < n; right++) {
            count[s[right]]--;
            while (IsBalanced()) {
                minLength = Math.Min(minLength, right - left + 1);
                count[s[left]]++;
                left++;
            }
        }

        return minLength;
    }
}

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