Задача с собеседования в Яндекс

Для заданной строки найти длину наибольшей подстроки без повторяющихся символов.
Например:
abcabcbbddee -> 3 (abc)
bbbbb -> 1 (b)
pwwkew -> 3 (wke)

Решить желательно за линию

Решение:

Решение сложнее O(N) - плохо
С двумя проходами по строке - нормально
С одним проходом по строке - хорошо

Для каждой позиции будем находить самую длинную подстроку, заканчивающуюся в данной позиции. Если мы нашли ответ для позиции i (обозначим за P[i]) - легко посчитать ответ для позиции i + 1: для этого надо найти самое правое вхождение символа S[i+1] в префиксе S[1...i] и взять максимум из найденной позиции и P[i].
Если символов мало, то последнее вхождение каждого символа можно поддерживать в массиве, иначе его стоит хранить в hash_map (это важно уточнить у собеседующего)
Решение за O(N)

Также не забываем в реализации проверить
1) Работу на пустой строке и строке из одного символа
2) Ответ для любой непустой строки хотя бы 1

@algoses