Вы разрабатываете препроцессор текста для языковой модели. Пользователи иногда тянут буквы, например: coooool, yaaaау. Перед обучением модели и при обработке пользовательских…
Вы разрабатываете препроцессор текста для языковой модели. Пользователи иногда тянут буквы, например: coooool, yaaaау. Перед обучением модели и при обработке пользовательских сообщений такие повторения нужно нормализовать: каждая подряд идущая серия одинаковых символов должна иметь длину не больше К. По заданным К и строке 5 (состоящей из латинских букв) получите строку 5, в которой длина каждой максимальной серии одинаковых символов не превосходит К. Не меняйте порядок символов и не удаляйте серии полностью. Формат входных данных Первая строка содержит натуральное число К > 1. Вторая строка содержит строку из латинских букв (А..Z, a..z). Формат выходных данных Выведите исправленную строку.
Задача сводится к нормализации повторяющихся подряд одинаковых символов в строке: каждая максимальная последовательность одинаковых букв должна иметь длину не больше заданного K (при этом порядок символов не изменяется, а сами серии не удаляются полностью — лишние повторения просто обрезаются до длины K).
Пошаговый разбор алгоритма
- Вход: натуральное число K (>1) и строка s, состоящая из латинских букв.
- Цель: пройти по строке и для каждой новой буквы:
- если она та же, что и предыдущая, то добавлять её можно только пока длина текущей серии не достигла K;
- если серия уже достигла K, лишние повторения пропускать (не добавлять).
- если буква другая, начать новую серию с длиной 1.
- Выход: новая строка, в которой все максимальные серии одинаковых символов имеют длину не более K.
Алгоритм в виде простых шагов
- Прочитать K и строку s.
- Создать пустой результат и следить за предыдущим символом и длиной текущей серии.
- Пройти по каждому символу ch в s:
- если ch == текущий_предыдущий и длина серии < K, добавить ch и увеличить длину серии;
- если ch == предыдущий и длина серии == K, пропустить (не добавлять);
- если ch != предыдущий, добавить ch, сделать новую серию: предыдущий = ch, длина = 1.
- Вернуть объединённую строку результата.
Сложность: время O(n), где n — длина входной строки; память O(1) помимо самой выходной строки.
Пример
- Ввод:
- K = 2
- s = "coooo" (длина 5)
- Обработка: "c" (1), затем "o" повторяется 4 раза, но лимит K=2, значит остаются первые 2 'o': итог "coo"
- Вывод: coo
Реализация на Python (простой и понятный вариант)
- Функция нормализации:
- вход: K, s
- выход: строка с ограниченными сериями
def normalize_runs(K, s): res = [] prev = None count = 0 for ch in s: if ch == prev: if count < K: res.append(ch) count += 1 # иначе пропускаем else: res.append(ch) prev = ch count = 1 return ''.join(res)
Пример использования через ввод-вывод
- Пример входных данных:
- 2
- coooo
- Пример вывода:
- coo
Полная работа программа (чтение из stdin и вывод в stdout)
- Код:
def normalize_runs(K, s): res = [] prev = None count = 0 for ch in s: if ch == prev: if count < K: res.append(ch) count += 1 else: res.append(ch) prev = ch count = 1 return ''.join(res)
if name == "main": import sys data = [line.strip() for line in sys.stdin if line.strip() != ''] if len(data) >= 2: K = int(data[0]) s = data[1] print(normalize_runs(K, s))
Замечания
- Поскольку условие говорит, что K > 1, мы не столкнемся с нулевой длиной серии.
- Если входная строка короче или длиннее 5 символов, алгоритм работает корректно для любой длины: он просто ограничивает длину каждой серии до K.
- Этот подход сохраняет первоначальный порядок символов и не удаляет целые серии, за исключением лишних повторений внутри серии, необходимых для удовлетворения ограничения по длине K.
