Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Вы разрабатываете препроцессор текста для языковой модели. Пользователи иногда тянут буквы, например:…
Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Вы разрабатываете препроцессор текста для языковой модели. Пользователи иногда тянут буквы, например: coooool, yaaaay. Перед обучением модели и при обработке пользовательских сообщений такие повторения нужно нормализовать: каждая подряд идущая серия одинаковых символов должна иметь длину не больше К. По заданным К и строке S (состоящей из латинских букв) получите строку S', в которой длина каждой максимальной серии одинаковых символов не превосходит К. Не меняйте порядок символов и не удаляйте серии полностью. Формат входных данных Первая строка содержит натуральное число K > 1. Вторая строка содержит строку S из латинских букв (А…Z, а…2). Формат выходных данных Выведите исправленную строку. Ввод 2 uraaaaSuperrr Вывод uraaSuperr Найди ответ
Идея: пройти по строке и для каждой максимальной последовательности одинаковых символов оставить не более K повторов. То есть для каждого блока подряд идущих одинаковых символов берем min(длина блока, K) копий этого символа.
Алгоритм:
- пройти по строке слева направо, считать длину текущего блока одинаковых символов.
- при смене символа добавлять в результат текущий символ, повторенный min(длина блока, K) раз.
- в конце обработать последний блок.
Сложность: O(n) по длине строки, память O(n) для результирующей строки.
Пример: K = 2, S = "uraaaaSuperrr" -> "uraaSuperr".
Код (Python):
def solve(): import sys data = sys.stdin.read().split() if not data: return K = int(data[0]) S = data[1] if len(data) > 1 else ""
if not S:
print("")
return
res = []
prev = S[0]
cnt = 1
for ch in S[1:]:
if ch == prev:
cnt += 1
else:
res.append(prev * min(cnt, K))
prev = ch
cnt = 1
res.append(prev * min(cnt, K))
sys.stdout.write("".join(res))
if name == "main": solve()
