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

Пояснение к подходу

• Пройдем по строке S один раз и будем строить результат постепенно.
• Будем держать текущий символ и его длину в текущей последовательности.
• При встрече нового символа начинаем новую последовательность и добавляем первый символ новой серии в выход.
• При встрече того же символа увеличиваем длину последовательности и добавляем символ в выход только если длина последовательности не превысила K.
• Так каждая серия будет состоять не более чем из K одинаковых символов.

Алгоритм (псевдокод)

• считать K
• считать S
• если S пустая, вернуть ""
• будет результат как массив символов: res = []
• cur = S[0]
• count = 1
• положить cur в res
• для каждого ch в S[1:]:
  • если ch == cur:
    • count += 1
    • если count <= K: добавить ch в res
  • иначе:
    • cur = ch
    • count = 1
    • добавить ch в res
• вернуть строку из res

Сложность

• Временная: O(n), где n = длина S
• Память: O(n) на выходную строку (и константные доп. переменные)

Пример

• Ввод: K = 2, S = "aaabbbaa"
• Обработка даст: "aabbb"? Нет: разберем по шагам
  • "aa" (первый пакет 'a' обрезан до 2) → "aa"
  • затем "bbb" → обрезано до "bb" → "aabb"
  • затем "aa" (два 'a') → добавляем "aa" → "aabbaa"
• Вывод: "aabbaa"

Код на Python (рабочий пример) def normalize_runs(K, S): if not S: return "" res = [] cur = S[0] count = 1 res.append(cur) for ch in S[1:]: if ch == cur: count += 1 if count <= K: res.append(ch) else: cur = ch count = 1 res.append(ch) return "".join(res)

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

K = 2

S = "aaabbbaa"

print(normalize_runs(K, S)) # -> "aabbaa"

Советы по тестированию

• Тестируйте границы: K = 2, K = 10; строки без повторов; строки, где один длинный повтор больше K; пустая строка.
• Примеры:
  • K=3, S="aaabbbccc" -> "aaabbbccc"
  • K=2, S="aaabbbaaa" -> "aabb aa"? точнее: "aabb aaa" без пробелов: "aabb aa"? В точности: "aabb aa" → без пробелов: "aabb aa" неправильно. Правильный результат: "aabb aa" слитно = "aabbaa".
  • K=2, S="abcde" -> "abcde" (нет повторов длиннее 2)

Если хочешь, могу адаптировать решение под другой язык программирования или привести пошаговый разбор на конкретном примере.