Зафиксируйте длину текущего валидного окна как кандидата на максимум, затем продолжите движение правой границы. Считать ответ до восстановления инварианта нельзя.
Что делать после сжатия скользящего окна
Зафиксируйте длину текущего валидного окна как кандидата на максимум, затем продолжите движение правой границы. Считать ответ до восстановления инварианта нельзя.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Алгоритм ищет самую длинную подстроку без повторяющихся символов. После добавления правого символа левая граница сдвигается до устранения дубля. Какой следующий шаг?
Ответ
Зафиксируйте длину текущего валидного окна как кандидата на максимум, затем продолжите движение правой границы. Считать ответ до восстановления инварианта нельзя.
Длина включительного окна равна right−left+1. Частоты или последние позиции должны отражать именно текущее окно. Левая граница не должна двигаться назад, иначе повторно включатся уже исключённые символы. Каждый указатель проходит строку не более одного раза, поэтому корректная реализация имеет линейное время.