Что спрашивают
Строка содержит заглавные латинские буквы. Найдите максимальную длину непрерывного фрагмента, в котором нет ни G, ни W, ни P. В связанной задаче длина строки достигает 1 200 000 символов; подходящий фрагмент существует.
Непрерывный фрагмент нельзя собирать из отдельных участков. Запрещённая буква разрывает серию: символы по разные стороны от неё не объединяются.
Приём решения
Достаточно хранить два числа: длину подходящей серии, заканчивающейся прямо сейчас, и наибольшую найденную длину. Если очередная буква разрешена, текущая серия увеличивается на единицу. Если запрещена, серия становится пустой, то есть её длина равна нулю.
- Начните с
current = best = 0. - Для каждой буквы проверьте принадлежность множеству запретов
GWP. - После изменения текущей длины обновите максимум.
- После последнего символа выведите
best.
После каждой позиции current равен длине самого длинного разрешённого суффикса уже прочитанной части. Других кандидатов с тем же правым концом искать не нужно: они короче. Перебирая все правые концы, получаем общий максимум.
Храним длину, а не накапливаем саму подстроку через current_text += ch. Так состояние занимает постоянную память, а обработка — O(n) времени. Сама входная строка занимает O(n) памяти.
Разбор на примере
Ввод
AGBCDWEFPRSTU
Вывод
4
| Участок | Что происходит | Лучшая длина |
|---|---|---|
| A | Серия длины 1 | 1 |
| G | Сброс | 1 |
| BCD | Серия длины 3 | 3 |
| W, затем EF | Сброс и новая серия | 3 |
| P, затем RSTU | Последняя серия длины 4 | 4 |
Запрещённые буквы делят строку на фрагменты A, BCD, EF и RSTU. Самый длинный заканчивается вместе со строкой и содержит четыре символа. Максимум обновляется внутри прохода, поэтому отдельная обработка хвоста не нужна.
Код на Python и C++
Проверяется весь набор G, W, P. Остальные заглавные буквы допустимы; длина последней серии учитывается тем же обновлением максимума.
В C++ строку читает getline. Если файл записан в Windows, а программа запущена в Linux, в конце строки может остаться символ \r, поэтому программа убирает его вручную.
import sys
def solve(s):
current = best = 0
for ch in s:
if ch in 'GWP':
current = 0
else:
current += 1
best = max(best, current)
return best
if __name__ == '__main__':
print(solve(sys.stdin.readline().rstrip('\r\n')))
<algorithm>
<iostream>
<string>
using namespace std;
int solve(const string& s) {
int current = 0, best = 0;
for (char ch : s) {
if (ch == 'G' || ch == 'W' || ch == 'P')
current = 0;
else
current += 1;
best = max(best, current);
}
return best;
}
int main() {
string s;
getline(cin, s);
if (!s.empty() && s.back() == '\r')
s.pop_back();
cout << solve(s) << endl;
}
Типичные ошибки
- Исключить только одну букву
Условие запрещает три конкретных символа. Проверка только G оставит в ответе фрагменты с W или P.
- Считать общее количество разрешённых букв
Нужна непрерывная серия. После запрещённого символа текущую длину нужно обнулить, а не продолжать счёт.
- Ограничить разрешённый алфавит несколькими буквами
Разрешены все заглавные латинские буквы, кроме указанных трёх. Сверяйте набор с условием, не с коротким примером.