Если вместо сета использовать словарь, в котором значение это индекс последнего вхождения символа, то цикл while можно убрать и сразу сдвигать указатель до нужной позиции
Единственное что нужно не забыть - взять max(l, char_dict[s[r]]), а не просто char_dict[s[r]]. Это для случая, когда дублирующий символ уже и так выпал из текущего sliding window.
Зачем рисовать схему(как делаю я), если можно показать всё руками(как делает Алина)? 😁 P.S. Не хочу расстраивать автора видео, но тут всё же квадратичная(О(n^2)) сложность по времени. Ведь учитывается худший случай.
на джаве ооочень хочу контент!Девушка прекрасна
Если вместо сета использовать словарь, в котором значение это индекс последнего вхождения символа, то цикл while можно убрать и сразу сдвигать указатель до нужной позиции
Единственное что нужно не забыть - взять max(l, char_dict[s[r]]), а не просто char_dict[s[r]]. Это для случая, когда дублирующий символ уже и так выпал из текущего sliding window.
У вас алгоритм O(nk) можно за O(n), необходимо хранить текущий максиму допустимых вхождений, как бы переставая учитывать выпавшие символы!
нет там O(nk), ее решение работает за O(n)
Алгосики Качаем
Зачем рисовать схему(как делаю я), если можно показать всё руками(как делает Алина)? 😁
P.S. Не хочу расстраивать автора видео, но тут всё же квадратичная(О(n^2)) сложность по времени. Ведь учитывается худший случай.
Вы правы, Алексей.