Question

Текстовый файл состоит не более чем из $10^6$ символов латинского алфавита. Определите длину самой длинной непрерывной подпоследовательности, в которой символ Y встречается не более 100 раз.

Accepted Answer

169

Answer

Идея решения: найти все позиции символа Y в строке, затем для каждого окна из 101 вхождения Y (или меньше) вычислить длину подстроки между первым и последним Y в этом окне, включая промежутки.

Сначала прочитаем файл и соберём индексы всех вхождений Y:

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

positions = []
for i in range(len(s)):
    if s[i] == 'Y':
        positions.append(i)
```

Если Y встречается не более 100 раз, вся строка удовлетворяет условию:

```python
if len(positions) <= 100:
    print(len(s))
```

Иначе переберём все окна из 101 последовательного вхождения Y. Для каждого окна длина подстроки от первого Y до последнего Y равна разности их индексов плюс 1:

```python
else:
    max_length = 0
    for i in range(len(positions) - 100):
        # Окно: positions[i] до positions[i+100]
        length = positions[i + 100] - positions[i] + 1
        max_length = max(max_length, length)
    print(max_length)
```

Полный код:

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

positions = []
for i in range(len(s)):
    if s[i] == 'Y':
        positions.append(i)

if len(positions) <= 100:
    print(len(s))
else:
    max_length = 0
    for i in range(len(positions) - 100):
        length = positions[i + 100] - positions[i] + 1
        max_length = max(max_length, length)
    print(max_length)
```

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