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. Оба указателя двигаются только вперед, соответсвенно, общее количество операций пропорционально длине строки.