Question

Текстовый файл состоит не более чем из $10^6$ символов латинского алфавита. Определите длину минимальной подстроки, содержащей не менее 130 символов `W`. Для выполнения этого задания следует написать программу.

Accepted Answer

2086

Answer

Идея решения: найти все позиции символа `W` в строке, затем для каждого окна из 130 символов `W` вычислить длину подстроки между первым и последним символом этого окна.

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

```python
f = open('24.txt')
s = f.readline()
positions = []
for i in range(len(s)):
    if s[i] == 'W':
        positions.append(i)
```

Затем переберём все окна, содержащие ровно 130 символов `W`. Для каждого окна длина подстроки равна разности между позицией 130-го символа `W` и позицией первого символа `W` в окне, плюс 1:

```python
min_length = 10**10
for j in range(len(positions) - 129):
    length = positions[j + 129] - positions[j] + 1
    min_length = min(min_length, length)
print(min_length)
```

Полное решение:

```python
f = open('24.txt')
s = f.readline()
positions = []
for i in range(len(s)):
    if s[i] == 'W':
        positions.append(i)

min_length = 10**10
for j in range(len(positions) - 129):
    length = positions[j + 129] - positions[j] + 1
    min_length = min(min_length, length)
print(min_length)
```

Сложность: $O(n)$, где $n$ — длина строки.

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