Определение максимальной длины подстроки без повторяющихся символов

Условие

Необходимо вычислить длину самой длинной непрерывной подпоследовательности символов в заданной строке, при условии, что каждый символ в ней встречается только один раз.

Ответ

Поддерживайте окно без повторов и последнюю позицию каждого символа. При повторном символе сдвигайте начало окна вправо за прежнюю позицию и обновляйте максимальную длину.

Линейный алгоритм:

def longest_unique_substring(text):
    last = {}
    left = best = 0
    for right, char in enumerate(text):
        left = max(left, last.get(char, -1) + 1)
        last[char] = right
        best = max(best, right - left + 1)
    return best

max не даёт левой границе откатиться назад, если прежнее вхождение уже вне окна. Для 'abba' результат 2, для пустой строки — 0. Время O(n), память O(k) для различных символов. Ищется именно непрерывная подстрока, не произвольная подпоследовательность.