Не могу выполнить задание

Question

Условие: есть случайное слово длинной до 10^5. Мне нужно найти 2 одинаковых символа(особую подстроку) в этом слове, и посчитать сколько символов между этими двумя

Но если в строке несколько разных повторяющихся символов, например string="ETERNITY", то мне нужно найти самую длинную подстроку

Но также есть ограничение на выполнение кода - 1 секунда

Вот сам текст задания: Входные данные содержат одну строку, состоящую из заглавных латинских букв от 'A' до 'Z'. Строка не пустая и имеет длину, не превосходящую 10^5.

Выведите одно число - длину самой длинной подстроки, являющейся особой строкой

Вот одна из моих попыток написать это

text = "ETERNITY"
arr = []
for sym in text:
    arr.append(sym)
def ix(arr):
    n=len(arr)
    res=[]
    for i in range(n-1):
        for j in range(i+1,n):
            if arr[i]==arr[j]:
                res.append((i,j))
    return res
print(ix(arr))

Answer 1

Используем словарь.

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

s = "ETERNITY"
dict = {}
l, r = 0, 0
for i, c in enumerate(s):
    if c in dict:
        if i - dict[c] > r - l:
            l, r = dict[c], i
    else:
        dict[c] = i
print(s[l:r+1])

Вместо словаря можно даже список на 26 ячеек использовать + ord

Answer 2

Линейный алгоритм. Собираем позиции одинаковых символов в множества. Из всех множеств выбираем то у которого "размах" максимальный:

text = "ETERNITY"

d = {}
for i, c in enumerate(text):
    d.setdefault(c, set()).add(i)
print(1 + max(max(v) - min(v) for v in d.values()))

P.S. Не самое оптимальное решение (храним множества, а можно было бы хранить только минимум и максимум), но в ограничения укладывается и мало кода.

Без множеств (хранятся только первая и последняя позиции символа):

text = "ETERNITY"

d = {}
for i, c in enumerate(text):
    d.setdefault(c, [i, i])[1] = i
print(1 + max(v[1] - v[0] for v in d.values()))

Можно хранить только первые позиции символов и обновлять максимум на лету:

text = "ETERNITY"

max_dist = 1
first = {}
for i in range(len(text)):
    c = text[i]
    if c in first:
        dist = i - first[c]
        if dist > max_dist:
            max_dist = dist
    else:
        first[c] = i
print(1 + max_dist)

БЛОГ НА HUSL

Не могу выполнить задание

Ответы (2 шт):