Что спрашивают
Строка состоит из букв Q, R, W и цифр 1, 2, 4. Нужен самый длинный непрерывный фрагмент, в котором буквы и цифры чередуются. Начинаться и заканчиваться он может символом любого из двух типов.
Один символ подходит сам по себе. Разные символы не обязательно чередуются: например, Q и R — обе буквы.
Приём решения
Проверка зависит только от пары соседей. Если s[i - 1].isdigit() и s[i].isdigit() различаются, текущая серия продлевается. Иначе старая серия заканчивается перед текущим символом, а текущий символ начинает новую серию длины один.
- Для непустой строки положите текущую и лучшую длину равными единице.
- Перебирайте позиции со второй, сравнивая типы соседних символов.
- При разных типах прибавляйте единицу, при одинаковых присваивайте единицу.
- После каждого шага обновляйте максимум.
Почему после разрыва не ноль? Текущий символ уже прочитан и входит в новую серию. Она может продолжиться следующим символом другого типа. Поэтому в строке из одинаковых типов ответ всё равно не меньше единицы.
Каждая подходящая серия полностью определяется соседними парами внутри неё. Один проход проверяет все такие пары, поэтому время — O(n), дополнительная память счётчиков — O(1). Для длинной строки используем индексы, не создавая копию s[1:].
Разбор на примере
Ввод
44Q1R2W4RR
Вывод
8
| Позиции с нуля | Текущая серия | Длина |
|---|---|---|
| 0 | 4 | 1 |
| 1 | 4: одинаковый тип, новое начало | 1 |
| 1–7 | 4Q1R2W4 | 7 |
| 1–8 | 4Q1R2W4R | 8 |
| 9 | R: снова две буквы рядом | 1 |
Первая пара цифр разрывает чередование, но вторая цифра остаётся началом нового фрагмента. Дальше типы чередуются до предпоследней буквы R включительно. Получаем восемь символов. Последняя R продлить этот фрагмент не может.
Код на Python и C++
Входная строка непустая, поэтому начальное значение один корректно. Цифры и буквы в этой задаче только из заданного латинского алфавита.
В C++ функция isdigit из <cctype> возвращает не true или false, а число: ноль или не ноль. Перед сравнением результаты двух вызовов приводятся к bool.
import sys
def solve(s):
current = best = 1
for i in range(1, len(s)):
if s[i - 1].isdigit() != s[i].isdigit():
current += 1
else:
current = 1
best = max(best, current)
return best
if __name__ == '__main__':
print(solve(sys.stdin.readline().rstrip('\r\n')))
<algorithm>
<cctype>
<iostream>
<string>
using namespace std;
int solve(const string& s) {
int current = 1, best = 1;
for (size_t i = 1; i < s.size(); i++) {
if (bool(isdigit(s[i - 1])) != bool(isdigit(s[i])))
current += 1;
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;
}
Типичные ошибки
- Сравнивать символы вместо их типов
Проверка
a != bразрешит две разные буквы или две разные цифры подряд. Здесь сравниваются категории. - Разрешать начало только с буквы
Фрагмент может начинаться цифрой. Не отбрасывайте такие начала и не требуйте пары «буква + цифра» целиком.
- Обнулять длину после разрыва
Текущий символ уже образует новую серию длины один. Ноль приводит к потере символа на границе.