JuniorКодИногдаЕщё не отвечали
Длина наибольшей серии одинаковых символов
Дана строка s из строчных букв. Верните длину наибольшей подстроки, все символы которой одинаковы. Пустая строка возвращает 0.
Требования:
из каждого индекса».
- O(n) время, O(1) дополнительной памяти — один проход, а не O(n²) «скан вправо
int longestRun(const std::string& s) {
// ваш код здесь
}Допишите реализацию.
Пройдите один раз с текущей длиной серии. Пока следующий символ равен текущему, продлевайте серию; при смене сбрасывайте до 1. Отслеживайте максимальную длину серии за проход. Один проход, O(n) время, O(1) память; пустая строка даёт 0.
- ✗Сбрасывать длину серии в 0 вместо 1 при смене символа
- ✗Забывать сравнить последнюю серию с максимумом после цикла
- ✗Путать общую частоту символа с наибольшей непрерывной серией
- →Как расширить это до наибольшей подстроки с не более чем K различными символами?
- →Почему общая частота — не то же самое, что наибольшая серия?
Оглавление
Задача
Найдите длину наибольшей серии одинаковых символов за один проход O(n).
Решение
#include <string>
#include <algorithm>
int longestRun(const std::string& s) {
if (s.empty()) return 0;
int best = 1, cur = 1;
for (size_t i = 1; i < s.size(); ++i) {
if (s[i] == s[i - 1]) ++cur; // продлеваем серию
else cur = 1; // сброс на смене символа
best = std::max(best, cur);
}
return best;
}Ключевые моменты
- При смене символа серия сбрасывается в 1 (текущий символ уже идёт), а не в 0.
- Максимум обновляется на каждом шаге, поэтому отдельный flush последней серии не нужен.
- Это O(n); вариант «скан вправо из каждого индекса» — O(n²).
Оглавление
