JuniorКодЧастоЕщё не отвечали
Максимальное число подряд повторений для каждого символа
Для каждого различного символа строки выведите максимальное число его подряд идущих повторений в строке. Для "aaBaaaaBffc" ответ для a — 4, для B — 1, для f — 2, для c — 1.
Требования:
- O(n) время, один проход; сравнение чувствительно к регистру.
std::map<char,int> maxRepeats(const std::string& s) {
// ваш код здесь
}Допишите реализацию.
Идите по строке, отслеживая текущий символ и длину его серии. Когда символ меняется, обновите записанный максимум этого символа в таблице, если только что завершённая серия длиннее, затем начните новую серию длины 1. После цикла выведите последнюю серию. Один проход, O(n) время.
- ✗Выводить общую частоту вместо наибольшей непрерывной серии
- ✗Забывать вывести последнюю серию после окончания цикла
- ✗Сворачивать регистр, когда по условию надо учитывать его (или наоборот)
- →Почему сортировка ломает ответ для чередующегося символа вроде
aba? - →Как сохранить ключи вывода в порядке первого появления, а не отсортированными?
Оглавление
Задача
Для каждого символа выведите его наибольшее число подряд повторений за один проход O(n).
Решение
#include <string>
#include <map>
#include <algorithm>
std::map<char,int> maxRepeats(const std::string& s) {
std::map<char,int> best;
if (s.empty()) return best;
char prev = s[0]; int run = 1;
auto flush = [&](char c, int r) { best[c] = std::max(best[c], r); };
for (size_t i = 1; i < s.size(); ++i) {
if (s[i] == prev) ++run;
else { flush(prev, run); prev = s[i]; run = 1; }
}
flush(prev, run); // последняя серия
return best;
}Ключевые моменты
- Отслеживается непрерывная серия, а не общая частота (важно для
aba). - Последняя серия выводится после цикла отдельным flush.
- Сравнение чувствительно к регистру; один проход O(n).
Оглавление
