Question

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

Accepted Answer

3844

Answer

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

Сначала прочитаем файл и найдём все индексы, где встречается символ `T`:

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

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

```python
mini = 10**10
for j in range(len(pos) - 209):
    length = pos[j + 209] - 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) - 209):
    length = pos[j + 209] - pos[j] + 1
    mini = min(mini, length)
print(mini)
```

Альтернативный подход — разбить строку по символу `T` и восстанавливать подстроки:

```python
s = open('24.txt').readline()
parts = s.split('T')
mini = 10**9
for i in range(len(parts) - 208):
    substring = 'T' + 'T'.join(parts[i:i + 209]) + 'T'
    mini = min(mini, len(substring))
print(mini)
```

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