В длинной строке из небольшого конечного числа уникальных букв найдите самую длинную подстроку, содержащую все уникальные буквы, повторенные не более k раз
Я прочитал подобные вопросы и не могу найти ни одного уже опубликованного вопроса, похожего на мой.
Проблема: В длинной строке, состоящей из небольшого числа букв (алфавит этой строки относительно небольшой), найдите максимально длинную подстроку (сохраняя неизменный порядок), содержащую не более k повторений каждой буквы.
Пример: Входная строка xyzxyxxxxxzzz; к=2. Здесь у нас есть строка из алфавита {x, y, z}. Самыми длинными подстроками, в которых буквы не повторяются более двух раз, будут xyzxy или yzxyx.
Другой пример: abbbbcccddddabcd; к=1. Решения могут быть любыми: dabc, abcd.
Я не совсем понимаю, как формализовать решение в коде. Я думаю о подходе, при котором:
- строка читается слева направо, а количество каждого вхождения каждой уникальной буквы алфавита сохраняется, скажем, в словаре Python.
- если какая-либо буква повторяется более k раз, обрежьте строку перед оскорбительной буквой, сохраните ее в массиве возможных решений
- продолжить чтение строки до конца и сохранить любое возможное решение
- сделайте то же самое для подстроки исходной строки минус первая буква и вызывайте рекурсивно до тех пор, пока строка не будет исчерпана или у вас не останется меньше строки, чем уникальные буквы в алфавите
Почему-то мне кажется, что это было бы слишком сложно и должно быть более простое решение, которое очевидно, но по какой-то причине я его не вижу.
Это похоже на домашнее задание или на какую-то задачу с сайта по изучению алгоритмов (например, проекта Эйлера). Существуют ли какие-либо ограничения на то, какие (встроенные) модули или пакеты вы можете использовать?
Ответы 1
Ваш подход недалеко от эффективного решения. Лучше всего это работает с алгоритмом скользящего окна, где это окно может увеличиваться справа и уменьшаться слева. Итак, ваш второй шаг потребует изменений
Вместо:
если какая-либо буква повторяется более k раз, обрежьте строку перед оскорбительной буквой, сохраните ее в массиве возможных решений
Делать:
если какая-либо буква повторяется более k раз, обрежьте строку с левой стороны до первого появления этой оскорбительной буквы.
Рекурсия не нужна. На каждом этапе добавления символа справа от текущего окна проверяйте, не длиннее ли он лучшего, который у вас был до сих пор.
Выполнение:
from collections import defaultdict
def solve(s, k):
freq = defaultdict(int)
left = 0
bestLeft = 0
bestRight = -1
for right, ch in enumerate(s):
if freq[ch] < k:
freq[ch] += 1
else:
while s[left] != ch:
freq[s[left]] -= 1
left += 1
left += 1
if right - left > bestRight - bestLeft:
bestLeft, bestRight = left, right
return s[bestLeft: bestRight+1]
s = "xyzxyxxxxxzzz"
k = 2
print(solve(s, k)) # xyzxy
s = "abbbbcccddddabcd"
k = 1
print(solve(s, k)) # dabc
Что вы уже пробовали? Какой код у вас уже есть? Где ты застрял?