Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Вы разрабатываете препроцессор текста для языковой модели. Пользователи иногда тянут буквы, например:…
Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Вы разрабатываете препроцессор текста для языковой модели. Пользователи иногда тянут буквы, например: coooool, yaaaay. Перед обучением модели и при обработке пользовательских сообщений такие повторения нужно нормализовать: каждая подряд идущая серия одинаковых символов должна иметь длину не больше К. По заданным К и строке S (состоящей из латинских букв) получите строку S', в которой длина каждой максимальной серии одинаковых символов не превосходит К. Не меняйте порядок символов и не удаляйте серии полностью. Формат входных данных Первая строка содержит натуральное число K > 1. Вторая строка содержит строку S из латинских букв (А…Z, а…2). Формат выходных данных Выведите исправленную строку. Ввод 2 uraaaaSuperrr Вывод uraaSuperr
Алгоритм:
- Проходим по строке S слева направо.
- Следим за текущей серией одинаковых символов: хранится последний символ и его длина.
- При новом символе начинаем новую серию (добавляем его в итоговую строку).
- Если символ повторяется, увеличиваем счетчик и добавляем символ в результат только пока длина серии не превысит K. Далее повторения пропускаем.
Сложность: время O(|S|), память O(|S|) для результата.
Код (C++17):
#include <bits/stdc++.h> using namespace std;
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int K;
if (!(cin >> K)) return 0;
string S;
if (!(cin >> S)) return 0;
string res;
char last = '\0';
int cnt = 0;
for (char c : S) {
if (c != last) {
res.push_back(c);
last = c;
cnt = 1;
} else {
cnt++;
if (cnt <= K) res.push_back(c);
}
}
cout << res;
return 0;
}
Пример: Ввод: 2 uraaaaSuperrr Вывод: uraaSuperr
