Сложность: medium
Вам дана строка s длины n, содержащая только четыре вида символов: 'Q', 'W', 'E' и 'R'. Строка считается сбалансированной, если каждый из ее символов встречается n / 4 раз, где n - длина строки. Верните минимальную длину подстроки, которую можно заменить любой другой строкой той же длины, чтобы сделать s сбалансированной. Если s уже сбалансирована, верните 0.
Пример:
Input: s = "QWER"
Output: 0
👨💻 Алгоритм:
1⃣Проверка баланса:
Сначала проверим, сбалансирована ли строка s. Если да, то возвращаем 0.
2⃣Подсчет частоты символов:
Подсчитаем количество каждого символа в строке s.
3⃣Использование скользящего окна:
Используем метод двух указателей (скользящее окно) для нахождения минимальной подстроки, которую можно заменить, чтобы строка стала сбалансированной.
Начнем с окна, которое захватывает всю строку, и будем постепенно уменьшать его, проверяя при каждом шаге, становится ли строка сбалансированной.
😎 Решение:
def balancedString(s):
from collections import Counter
n = len(s)
count = Counter(s)
target = n // 4
def is_balanced():
return all(count[char] <= target for char in 'QWER')
if is_balanced():
return 0
min_length = n
left = 0
for right in range(n):
count[s[right]] -= 1
while is_balanced():
min_length = min(min_length, right - left + 1)
count[s[left]] += 1
left += 1
return min_length
Ставь 👍 и забирай 📚 Базу знаний