Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Вы разрабатываете препроцессор текста для языковой модели. Пользователи иногда тянут буквы, например:…

Задача понятна: дано число K > 1 и строка S, состоящая из латинских букв. Нужно привести каждую максимальную последовательность одинаковых символов к длине не более K, сохранив порядок символов и не удаляя полностью последовательности.

Пошаговое объяснение и решение

1. Идея

• Проходим по строке слева направо и считаем длину текущей последовательности одинаковых символов.
• Когда встречаем новый символ, дописываем в результат ту же букву повторённую min(длина последовательности, K) раз.
• После конца строки дописываем остаток текущей последовательности тем же способом.

2. Алгоритм

• Инициализируем текущий символ cur = S[0] и счётчик cnt = 1.
• По остальным символам прохода:
  • Если следующий символ равен cur, увеличиваем cnt.
  • Иначе дописываем в результат cur * min(cnt, K), меняем cur на новый символ и cnt = 1.
• В конце дописываем последнюю группу как cur * min(cnt, K).
• Соединяем все части в одну строку и выводим.

3. Сложность

• Временная: O(n), где n — длина S.
• Память: O(n) на результирующую строку.

4. Пример

• Вход: K = 2, S = "uraaaaSuperrr"
• Группы: 'u'(1), 'r'(1), 'a'(4), 'S'(1), 'u'(1), 'p'(1), 'e'(1), 'r'(3)
• Приводим к: 'u'(1), 'r'(1), 'a'(2), 'S'(1), 'u'(1), 'p'(1), 'e'(1), 'r'(2)
• Вывод: "uraaSuperr" (как в примере).

5. Реализация на Python

def normalize_runs(S, K): if not S: return "" res = [] cur = S[0] cnt = 1 for ch in S[1:]: if ch == cur: cnt += 1 else: res.append(cur * min(cnt, K)) cur = ch cnt = 1 res.append(cur * min(cnt, K)) return "".join(res)

def main(): import sys data = sys.stdin.read().splitlines() if not data: return K = int(data[0].strip()) S = data[1].strip() if len(data) > 1 else "" print(normalize_runs(S, K))

Пример использования:

• Ввод: 2 uraaaaSuperrr
• Вывод: uraaSuperr

Если нужны другие языки программирования, могу привести аналогичную реализацию на C++, Java или другом языке.