Question

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

Accepted Answer

1523

Answer

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

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

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

Теперь переберём все возможные окна из 100 символов 'T'. Для каждого окна от позиции `j` до позиции `j + 99` в массиве `pos` длина подстроки равна `pos[j + 99] - pos[j] + 1` (расстояние от первого до последнего символа 'T' в окне, включительно):

```python
mini = 10**10
for j in range(len(pos) - 99):
    length = pos[j + 99] - pos[j] + 1
    mini = min(mini, length)
print(mini)
```

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

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

mini = 10**10
for j in range(len(pos) - 99):
    length = pos[j + 99] - pos[j] + 1
    mini = min(mini, length)
print(mini)
```

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

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