Question

Текстовый файл состоит не более чем из 1 200 000 символов английского алфавита. Определите максимальное количество идущих подряд символов, среди которых символы Q, R, S в различных комбинациях (с учётом повторений) не стоят рядом.

Accepted Answer

544

Answer

Идея решения: найти максимальную длину подстроки, в которой никогда не встречаются два соседних символа из набора {Q, R, S}.

Логика работы: проходим по строке слева направо, отслеживая текущую длину последовательности символов, удовлетворяющих условию. Если текущий и предыдущий символы оба принадлежат множеству {Q, R, S}, то они стоят рядом — нарушение условия, и мы начинаем новую последовательность. В противном случае продолжаем текущую последовательность и обновляем максимум.

```python
s = open('24.txt').readline()
c = mx = 1
for i in range(1, len(s)):
    if s[i-1] not in 'QRS' or s[i] not in 'QRS':
        c += 1
        mx = max(mx, c)
    else:
        c = 1
print(mx)
```

Алгоритм работает за один проход по строке, сложность $O(n)$.

Задание №24ПрограммированиеЕГЭ по информатике