P.S
Да, в интернете существует множество решений подобных задач, но, по моим ощущениям, они написаны сложным языком для начинающего программиста. Особенно мало материалов с примерами на Go. Когда я обучался алгоритмам, мне казалось, что данные темы можно объяснить куда проще существующих.В этой статье я пошагово разберу технику "Sliding Window" ("Скользящее окно") и покажу, как с её помощью решить задачу Longest Substring Without Repeating Characters на Go.
Задача на Longest Substring Without Repeating Characters
Ссылка на задачу: https://leetcode.com/problems/longest-substring-without-repeating-characters
Given a string
s, find the length of the longest substring without duplicate characters.Дана строка s, в которой нужно найти длину самой длиной подстроки уникальных символов.
Начнём с базового понимания Sliding Window
Суть этой техники в том, чтобы использовать два указателя - left и right. Указатель right двигается слева направо, делая текущее окно шире. Если в окне появляется дубликат, указатель left двигается вправо до тех пор, пока подстрока снова не станет уникальной. При этом на каждом шаге мы обновляем переменную maxLen, в которой храним максимальную длину найденной уникальной подстроки.
Разберем сначала без кода
Возьмем s = "abba"
Итерация 0:
right = 0 (символ a имеет индекс 0)
текущее окно [a]bba
так как символа "a" нет в мапе - заносим его в мапу map[a] = 0
maxLen = max(maxLen, right - left + 1) = (0, 0 - 0 + 1) = 1
Итерация 1:
right = 1 (символ b имеет индекс 1)
текущее окно [ab]ba
так как символа "b" нет в мапе - заносим его в мапу map[b] = 1
maxLen = max(1, 1 - 0 + 1) = 2
Итерация 2:
right = 2 (второй символ b имеет индекс 2)
текущее окно [abb]a
символ уже встречался ранее, поэтому нужно проверить, находится ли его предыдущее вхождение внутри текущего окна
сокращение окна: left = 2 (так как нам надо сократить окно мы должны взять индекс предыдущего элемента map[b] = 1 и прибавить 1)
текущее окно стало ab[b]a
текущий максимум по прежнему maxLen = 2
Итерация 3:
right = 3 (второй символ a имеет индекс 3)
текущее окно ab[ba]
символ уже встречался ранее, поэтому нужно проверить, находится ли его предыдущее вхождение внутри текущего окна
индекс символа a (map[a] = 0) не входит в диапазон нашего окна, так как сейчас оно находится в [2,3]. Поэтому мы меняем значение в мапе на текущий индекс символа map[a] = 3
maxLen = max(2, 3 - 2 + 1) = 2
Ответ: 2
Вывод: После каждой итерации окно всегда содержит только уникальные символы
Приступим к реализации
Создаем переменные: left (левый указатель), maxLen (максимальная длина).
func lengthOfLongestSubstring(s string) int { left := 0 //Левый указатель maxLen := 0 //Максимальная длина уникальной подстроки }
Для хранения уникальных символов нам стоит использовать map (мапа, хеш-таблица), так как нам важна уникальность символов и скорость работы. Ключом будет символ, а значеним индекс этого символа в массиве.
func lengthOfLongestSubstring(s string) int { left := 0 //Левый указатель maxLen := 0 //Максимальная длина уникальной подстроки symbols := make(map[rune]int) //мапа для хранения уникальных символов }
Далее нам нужен цикл, чтобы пройтись по массиву, и именно здесь будет иницилизорован правый указатель right - тот самый, который идет слева направо.
func lengthOfLongestSubstring(s string) int { left := 0 //Левый указатель maxLen := 0 //Максимальная длина уникальной подстроки symbols := make(map[rune]int) //мапа для хранения уникальных символов for right, value := range s{ //right - это индекс нашего символа, а value - значение } }
Чтобы проверить наличие символа в мапе, нам нужно создать условие, получив значние по ключу (lastIndex). Здесь мы спрашиваем мапу, сущетсвует ли в ней символ: если ok == true - значит, существует. Также нам важно знать, находится ли его предыдущее вхождение внутри текущего окна. Для этого используется условие
lastIndex >= left. Если оно выполнится, значит, дубликат находится внутри текущего окна, и указатель left необходимо сдвинуть.
func lengthOfLongestSubstring(s string) int { left := 0 //Левый указатель maxLen := 0 //Максимальная длина уникальной подстроки symbols := make(map[rune]int) //мапа для хранения уникальных символов for right, value := range s{ //right - это индекс нашего символа, а value - значение if lastIndex, ok := symbols[value]; ok && lastIndex >= left { //lastIndex - значение в мапе по ключу left = lastIndex + 1 } } }
-
Если же такого символа не было или его индекс не находится в диапазоне текущего окна, то мы заносим его в мапу. Далее вычисляем длину текущего окна и обновляем максимальное значение. Формула длины подстроки выглядит так:
maxLen = max(maxLen, right - left + 1),где
right - left + 1- длина текущего окна.Для сравнения чисел я добавил простейшую функцию, которая определяет максимальное значение.
func lengthOfLongestSubstring(s string) int { left := 0 //Левый указатель maxLen := 0 //Максимальная длина уникальной подстроки symbols := make(map[rune]int) //мапа для хранения уникальных символов for right, value := range s{ //right - это индекс нашего символа, а value - значение if lastIndex, ok := symbols[value]; ok && lastIndex >= left { //lastIndex - значение в мапе по ключу left = lastIndex + 1 } symbols[value] = right //Заполняем мапу, где ключ - символ, а значние - его индекс maxLen = max(maxLen, right - left + 1) //считаем максимальную длину } } func max(a, b int) int { if a > b { return a } return b }
После всех шагов алгоритма, мы с ощущением победы, возвращаем maxLen (макисмальную длину подстроки из уникальных символов) из функции. Конечный вариант функции, реализующий технику Sliding Window, выглядит так:
func lengthOfLongestSubstring(s string) int { left := 0 //Левый указатель maxLen := 0 //Максимальная длина уникальной подстроки symbols := make(map[rune]int) //мапа для хранения уникальных символов for right, value := range s{ //right - это индекс нашего символа, а value - значение if lastIndex, ok := symbols[value]; ok && lastIndex >= left { //lastIndex - значение в мапе по ключу left = lastIndex + 1 } symbols[value] = right //Заполняем мапу, где ключ - символ, а значние - его индекс maxLen = max(maxLen, right - left + 1) //считаем максимальную длину } return maxLen //возвращаем максимальную длину подстроки уникальных символов } func max(a, b int) int { if a > b { return a } return b }
Асимптотическая сложность
Сложность по времени: O(n) - так как каждый символ обрабатывется не более двух раз. Один раз при расширении окна указателем right и, возможно, один раз при сужении окна указателем left. Оба указателя двигаются только вперед, соответсвенно, общее количество операций пропорционально длине строки.
Комментарии (27)
alcotel
08.03.2026 20:54А разве доступ к хэш-таблице занимает время О(1) ?
Bulgil
08.03.2026 20:54Именно так
alcotel
08.03.2026 20:54?
wataru
08.03.2026 20:54В среднем, действительно, у хеш-таблицы доступ за O(1).
alcotel
08.03.2026 20:54То есть, не зависит от размера таблицы?
Что-то я пропустил. Думал, лучший вариант - что-то типа O(log N)
wataru
08.03.2026 20:54Да, в среднем добавление, удаление и поиск в хеш таблице - O(1). В худшем случае O(N) вообще, но его считается практически невозможно подобрать в хороших реализациях.
То есть, не зависит от размера таблицы?
Как бы да. Вон в массиве доступ по индексу O(1). Тоже не зависит от размера. Именно на этом и строится хеш таблица.
alcotel
08.03.2026 20:54Точно, я как раз про сравнение хеш-таблиц с массивами. Специально почитал, как это реализовано (я не фанат Go, только учусь))) под капотом, и гарантированной скорости доступа не нашёл.
wataru
08.03.2026 20:54Вообще, в этой задаче не нужны даже никакие хеш-мапы. Нужен лишь массив на 26 элементов - по одному для каждого символа.
alcotel
08.03.2026 20:54Я про то же. В массиве же всё быстрее и гарантировано. Фишка алгоритма ведь в том, что изначальная скорость О(N²) разменивается на O(N) за счёт использования таблицы. Бесплатно ничего не бывает (c). Автор про это не заикнулся. Поэтому не-плюс автору.
Ну, про 26 многие национальные языки с вами не согласятся))) Ya by dazhe komment ne smog tut ostavit)) blya, probela tozhe net, i tolko kaps est. OXPEHETb!
wataru
08.03.2026 20:54Не совсем. Таблица нужна чтобы за константу пересчитывать метрику окна при добавлении/удалении одного элемента. Но если этот пересчет будет за O(n), то вы все-равно техникой скользящего окна соптимизируете уже с O(n^3) до O(n^2).
Даже в какой-то какой-то извращенной не аддитивной метрике где одинаково сложно изменить один элемент и пересчитать метрику всей подстроки с нуля, скользящее окно работает. Оно позволяет считать метрику максимум в 2n окнах. когда как перебор должен будет подсчитать n(n+1)/2 подстрок.
Ну, про 26 многие национальные языки с вами не согласятся
В конкретной задаче написано:
sconsists of English letters, digits, symbols and spaces.Так что я был не совсем прав. Достаточно 256 элементов.
alcotel
08.03.2026 20:54Не совсем понял про извращённую метрику. Про то, что окно принципиально меняет сложность - это да, естественно.
Я про то, что внутри цикла ( это О(n) сразу же ) я могу вызвать не
symbols[value], а, например, сортировку. И сказать: "Ну, я ж её вызвал один раз, значит она О(0), а что?"
wataru
08.03.2026 20:54Если общий случай оценивать, то сложность O(N(a+r)), где a,r - сложности пересчета метрики при добавлении/удалении метрики в окно. В этой задаче они O(1). Если вы каждый раз сортировку делаете, то будет O(N(2N logN)) = O(N^2 logN)
alcotel
08.03.2026 20:54Так это ВЫ понимаете, а не автор статьи. Поэтому на ваши статьи я подпишусь, и почитаю старые. А этого автора я послезавтра уже не вспомню.
wataru
08.03.2026 20:54Вообще, документация по go никаких гарантий не дает, но то, что map там unordered, как бы намекает, что для него используются хеш таблицы. И как я понял туда можно использовать ключи, для которых даже сравнение не реализовано. Так что деревья поиска тут отпадают вообще. Остается только хеш таблица.
Alexandroppolus
08.03.2026 20:54Думал, лучший вариант - что-то типа O(log N)
Это если словарь сделан не как хэш-мап, а на основе дерева. Например, std::map.
wataru
Пишите, что статья объясняет проще, но я считаю, что написана она не очень хорошо. Как обычно, тем, кто задачи решать умеет, ваша статья не нужна, тем кто не умеет - она не очень поможет.
Начнем с того, что надо дать определение окна. Почему оно sliding. Аналогию с хотя бы с двумя картонками. которыми закрывают часть массива слева и справа (ибо логарифмические линейки уже никто и не представляет себе).
Главный косяк - вы объясняете что, а не почему и как к этому прийти.
Вы начинаете объяснять решение с указателей, и говорите про дубликаты в окне, но к этому моменту еще не сказали, что вообще за окно такое.
Потом вы объясняете действия "без кода", но там ссылаетесь на какой-то map.
Как обычно в подобных статьях, вы в тексте описываете код, а не объясняете почему код именно такой.
Ну и никакого обобщения принципа вы не даете. Решение конкретно этой задачи по вашей статье еще можно выучить, но уже соседнюю задачу на такое же скользящее окно прочитавший вашу статью не решит.
Почему вообще в задаче на длиннейшую подстроку с каким-то свойством возникает окно? Потому что свойство "наследуемое" - если оно выполняется для какой-то строки, то и для всех в нее вложенных - тоже. Поэтому можно вообще все подстроки сгруппировать по, допустим, концу. Для каждого фиксированного конца в ответ идут строки с последовательными длинами с одного символа и до какой-то самой длинной строки. Эту самую длинную строку мы и ищем, потом среди всех различных концов остается взять максимум. Скользящее окно как раз и будет представлять собой эту самую наидлиннейшую подстроку с фиксированным концом.
Еще эту задачу можно решать с другого конца. Мне кажется, такое объяснение было бы понятнее. Начните с наивного решения с двумя вложенными циклами, где перебираете начало и потом конец, а внутри считаете циклом - есть ли дубликаты в подстроке с мапой. Это кубическое решение. Потом заметьте, что при удлинении строки можно пересчитать проверку дубликата просто обработав один новый символ, поэтому не надо для каждого конца гнать вложенный третий цикл, можно двумя циклами все обработать. Вот уже квадратичное решение. Потом заметьте, что при сдвиге начала в право на 1 позицию у вас ответ будет не короче ответа для предыдущей строки -1. Так что можно не двигать указатель конца циклом с самого начала, а сразу оставить там, где он и был. Вот и возникло окно и решение за линию. Вот и нарисовалось скользящее окно.
La_Flame Автор
Часть замечаний действительно справедлива — например, про то, что можно было подробнее ввести само понятие окна и дать более явную аналогию. Это можно улучшить, и, возможно, я добавлю такой раздел в статью.
Однако цель материала была немного другой. Я не ставил задачу выводить технику sliding window через цепочку оптимизаций O(n³) → O(n²) → O(n). Такой подход действительно хорошо работает в учебных разборах алгоритмов, но он значительно увеличивает объем статьи и смещает фокус с самой техники на историю ее вывода.
В статье я сознательно пошел от практического применения: показать, как работает окно, как двигаются указатели и как поддерживается состояние структуры данных (map) внутри окна. Для читателей, которые уже встречали задачи на строки и два указателя, такой формат обычно оказывается более прямолинейным.
При этом идея «наследуемого свойства» подстрок, о которой вы пишете, действительно является одной из причин, почему sliding window вообще применим в подобных задачах. Это хорошее дополнение к теме, но оно выходит немного за рамки конкретного разбора задачи, который был основной целью статьи.
В любом случае спасибо за подробную обратную связь
wataru
Я считаю что это и должно быть фокусом в статьях для начинающих. Иначе это как пытаться зубрить формулу решения системы линейных уравнений вместо объяснения что можно строки друг из друга вычитать и таким образом получить нули выше диагонали.
Ну вот в этой задаче читатель поймет как применять map. А в задаче, где надо найти наибольший подмассив с суммой не больше заданной, уже не факт что поймет, что вместо мапа нужна сумма. Не объясняя принципы на которых решение строится вы не даете читателю никакой возможности решение обобщать. Это можно было бы обойти разобрав сразу 3-5 задач, обратив внимание что там меняется от задачи к задаче.
Alexandroppolus
Наследуемое оно в данной конкретной ситуации, но не в общем случае (например, "найти самую длинную подстроку, в которой К различных символов" - тоже окно), потому, имхо, лучше не упоминать.
wataru
Эта задача тождественна задаче найти "самую длинную подстроку, где не более K различных символов" (если в строке вообще есть хотя бы K различных символов). Ведь, если подстрока содержит меньше K символов, то ее можно расширить, прибавится максимум 1 новый символ и условие все еще выполнится.
А это свойство уже наследуемо.
Alexandroppolus
То есть каждая задача с наибольшей подстрокой и окном сводится к "наследуемой"?
wataru
Я думаю да. В некоторых задачах, где свойство меняется не "непрерывно", а скачакми, и может перескочить искомое значение придется обработать частный случай - наидлиннейшее окно <= K штук может иметь <K штук и в ответ его брать не надо. Но суть остается такой же: за счет наследуемости можно сократить решение с O(n^2) до O(n).
lightln2
А есть какой-то стандартный шаблон для sliding window, который позволяет для разных задач подставлять реализацию (как, например, с бинпоиском), или там слишком много разных вариаций? Ну, типа
И, кстати, почему-то везде все итерируют по правому концу, и подбирают левый, хотя, кажется, итерировать по левому концу немного более естесственно?
wataru
Есть. Именно как у вас. Только в общем случае add и remove принимают еще и индекс элемента. Мало ли что там за метрика. Но, покуда метрика наследуема - если какое-то окно good(), то любой его подмассив тоже - это работает.
Можно итерировать и по другому концу. Но тут 2 варианта: если вы цикл с задом наперед гоните, то это фактически абсолютно тоже самое и будет, только на развернутом массиве. Если же вы двигаете в цикле left с 0 до n, и right подстраиваете, то там надо будет "заглядывать вперед". Вы увеличиваете right, если следующее окно будет хорошее. Или поддерживать инвариант, что right - это первый плохой элемент. Ну и появляется отдельный вариант, когда left обгоняет right.
Не велика разница, и то и другое выводится: фиксируем или конец или начало и двигаем другой максимально дальше. Потом переходим к следующему фиксированному концу и отодвигаем второй конец в ту же сторону, пока надо.
Кому-то один кажется интуитивнее, кому-то другой. Мне кажется исходный вариант чуть проще. Там на одну проверку меньше и код обработки окна и проверки ответа разделяется. Во втором варианте окно надо обрабатывать до проверки ответа и после.