Question

Текстовый файл состоит не более чем из $10^7$ строчных букв английского алфавита. Найдите максимальную длину подстроки, в которой символы *a* и *d* не стоят рядом друг с другом.

Accepted Answer

2252

Answer

Идея решения: отслеживать длину текущей подстроки, которая не содержит пар «ad» или «da», и обновлять максимум при каждом нарушении условия.

Проходим по строке со второго символа. Для каждой позиции проверяем, образуют ли предыдущий и текущий символы запрещённую пару. Если нет — увеличиваем счётчик длины текущей подстроки, иначе обнуляем его и начинаем считать заново. После каждого шага обновляем максимальное значение.

```python
f = open('24.txt')
s = f.readline()

c = 1
m = 0

for i in range(1, len(s)):
    if s[i-1:i+1] not in ['da', 'ad']:
        c += 1
    else:
        c = 1
    m = max(m, c)

print(m)
```

Альтернативный подход — заменить все вхождения пар «ad» и «da» на разделённые пробелом версии, затем найти максимальную длину среди получившихся слов:

```python
f = open('24.txt')
s = f.readline()
s = s.replace('ad', 'a d').replace('da', 'd a')
print(max(map(len, s.split())))
```

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