Самая длинная подстрока без повторяющихся символов

Решение: Самая длинная подстрока без повторяющихся символов

Основная идея: Sliding Window

Используем два указателя (левый и правый):

1. Правый указатель движется вперёд, добавляя символы
2. Если встретили повторение, движем левый указатель
3. Отслеживаем максимальную длину

Оптимальная реализация O(n)

func lengthOfLongestSubstring(s string) int {
    // Map для хранения последнего индекса каждого символа
    charIndex := make(map[rune]int)
    maxLength := 0
    left := 0 // Левый указатель окна
    
    for right := 0; right < len(s); right++ {
        char := rune(s[right])
        
        // Если символ повторяется и находится в текущем окне
        if idx, exists := charIndex[char]; exists && idx >= left {
            // Передвигаем левый указатель за предыдущее вхождение
            left = idx + 1
        }
        
        // Запоминаем индекс текущего символа
        charIndex[char] = right
        
        // Обновляем максимальную длину
        currentLength := right - left + 1
        if currentLength > maxLength {
            maxLength = currentLength
        }
    }
    
    return maxLength
}

Сложность:

• Время: O(n) — один проход по строке
• Память: O(min(n, m)) — где m это размер алфавита (ASCII: 128, Unicode: ~1M)

Пошаговый пример для "abcabcbb"

Индекс: 0 1 2 3 4 5 6 7
Строка: a b c a b c b b

Шаг 1: right=0, char='a'
  charIndex={'a': 0}
  left=0, length=1, maxLength=1

Шаг 2: right=1, char='b'
  charIndex={'a': 0, 'b': 1}
  left=0, length=2, maxLength=2

Шаг 3: right=2, char='c'
  charIndex={'a': 0, 'b': 1, 'c': 2}
  left=0, length=3, maxLength=3

Шаг 4: right=3, char='a' (ПОВТОРЕНИЕ!)
  'a' уже в charIndex с индексом 0 >= left(0)
  left = 0 + 1 = 1
  charIndex={'a': 3, 'b': 1, 'c': 2}
  length = 3-1+1 = 3, maxLength=3

Шаг 5: right=4, char='b' (ПОВТОРЕНИЕ!)
  'b' уже в charIndex с индексом 1 >= left(1)
  left = 1 + 1 = 2
  charIndex={'a': 3, 'b': 4, 'c': 2}
  length = 4-2+1 = 3, maxLength=3

Шаг 6: right=5, char='c' (ПОВТОРЕНИЕ!)
  'c' уже в charIndex с индексом 2 >= left(2)
  left = 2 + 1 = 3
  charIndex={'a': 3, 'b': 4, 'c': 5}
  length = 5-3+1 = 3, maxLength=3

Шаг 7: right=6, char='b' (ПОВТОРЕНИЕ!)
  'b' уже в charIndex с индексом 4 >= left(3)
  left = 4 + 1 = 5
  charIndex={'a': 3, 'b': 6, 'c': 5}
  length = 6-5+1 = 2, maxLength=3

Шаг 8: right=7, char='b' (ПОВТОРЕНИЕ!)
  'b' уже в charIndex с индексом 6 >= left(5)
  left = 6 + 1 = 7
  charIndex={'a': 3, 'b': 7, 'c': 5}
  length = 7-7+1 = 1, maxLength=3

Результат: maxLength = 3

Альтернатива: с массивом вместо map (для ASCII)

func lengthOfLongestSubstring(s string) int {
    // Массив для ASCII символов (256)
    lastIndex := make([]int, 256)
    for i := range lastIndex {
        lastIndex[i] = -1 // Изначально -1 означает символ не встречался
    }
    
    maxLength := 0
    left := 0
    
    for right := 0; right < len(s); right++ {
        char := s[right]
        
        // Если символ был в текущем окне
        if lastIndex[char] >= left {
            left = lastIndex[char] + 1
        }
        
        lastIndex[char] = right
        
        currentLength := right - left + 1
        if currentLength > maxLength {
            maxLength = currentLength
        }
    }
    
    return maxLength
}

Преимущество: Немного быстрее для ASCII (array lookup vs map lookup) Недостаток: Фиксирован размер (256), не работает корректно для всех Unicode

Версия с возвращением самой подстроки

func lengthOfLongestSubstringWithString(s string) (int, string) {
    charIndex := make(map[rune]int)
    maxLength := 0
    maxStart := 0
    left := 0
    
    for right := 0; right < len(s); right++ {
        char := rune(s[right])
        
        if idx, exists := charIndex[char]; exists && idx >= left {
            left = idx + 1
        }
        
        charIndex[char] = right
        
        currentLength := right - left + 1
        if currentLength > maxLength {
            maxLength = currentLength
            maxStart = left
        }
    }
    
    return maxLength, s[maxStart : maxStart+maxLength]
}

Примеры работы

func main() {
    fmt.Println(lengthOfLongestSubstring("abcabcbb"))  // 3
    fmt.Println(lengthOfLongestSubstring("bbbbb"))     // 1
    fmt.Println(lengthOfLongestSubstring("pwwkew"))    // 3
    fmt.Println(lengthOfLongestSubstring(""))          // 0
    fmt.Println(lengthOfLongestSubstring("au"))        // 2
    fmt.Println(lengthOfLongestSubstring("dvdf"))      // 3 (vdf)
}

Версия с Unicode поддержкой

func lengthOfLongestSubstring(s string) int {
    // Конвертируем в runes для корректной работы с Unicode
    runes := []rune(s)
    charIndex := make(map[rune]int)
    maxLength := 0
    left := 0
    
    for right := 0; right < len(runes); right++ {
        char := runes[right]
        
        if idx, exists := charIndex[char]; exists && idx >= left {
            left = idx + 1
        }
        
        charIndex[char] = right
        
        currentLength := right - left + 1
        if currentLength > maxLength {
            maxLength = currentLength
        }
    }
    
    return maxLength
}

Тестирование

func TestLongestSubstring(t *testing.T) {
    tests := []struct {
        input    string
        expected int
    }{
        {"abcabcbb", 3},
        {"bbbbb", 1},
        {"pwwkew", 3},
        {"", 0},
        {"au", 2},
        {"dvdf", 3},
        {"abcdefghijk", 11},
    }
    
    for _, test := range tests {
        result := lengthOfLongestSubstring(test.input)
        if result != test.expected {
            t.Errorf("Input: %s, Expected: %d, Got: %d", test.input, test.expected, result)
        }
    }
}

Ключевые моменты

• Sliding Window: два указателя движутся по строке
• Map для индексов: храним последнее вхождение каждого символа
• Условие idx >= left: проверяем, что символ в текущем окне
• O(n) время: каждый символ посещается ровно дважды (right и left)
• O(min(n, m)) память: максимум все уникальные символы в map
• Нет вложенных циклов: это очень быстро для больших строк

Когда использовать

• Поиск подпоследовательностей с уникальными элементами
• Компрессия данных (поиск повторений)
• Парсинг и валидация токенов
• Анализ текста

Это классическая задача, которая показывает мастерство в работе с алгоритмами и структурами данных.