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

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

Концепция скользящего окна

Эта задача идеально решается техникой скользящего окна (sliding window). Идея в том, что мы используем два указателя (left и right) для создания окна, которое расширяется и сжимается, всегда сохраняя условие уникальности символов. Это позволяет решить задачу за один проход.

Базовое решение

function lengthOfLongestSubstring(s) {
  // Ассоциативный массив для сохранения индекса последнего символа
  const charIndex = {};
  let maxLength = 0;
  let left = 0;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    
    // Если символ уже встречался в текущем окне
    if (char in charIndex && charIndex[char] >= left) {
      // Сдвигаем левый указатель за предыдущее вхождение
      left = charIndex[char] + 1;
    }
    
    // Обновляем индекс текущего символа
    charIndex[char] = right;
    
    // Обновляем максимальную длину
    maxLength = Math.max(maxLength, right - left + 1);
  }
  
  return maxLength;
}

Версия с отслеживанием саму подстроку

function lengthOfLongestSubstring(s) {
  const charIndex = {};
  let maxLength = 0;
  let left = 0;
  let maxStart = 0;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    
    // Если символ повторяется в окне
    if (char in charIndex && charIndex[char] >= left) {
      left = charIndex[char] + 1;
    }
    
    charIndex[char] = right;
    
    // Если нашли новый максимум
    if (right - left + 1 > maxLength) {
      maxLength = right - left + 1;
      maxStart = left;
    }
  }
  
  return {
    length: maxLength,
    substring: s.substring(maxStart, maxStart + maxLength)
  };
}

TypeScript версия

function lengthOfLongestSubstring(s: string): number {
  const charIndex: Record<string, number> = {};
  let maxLength: number = 0;
  let left: number = 0;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    
    // Если символ уже в окне
    if (char in charIndex && charIndex[char] >= left) {
      left = charIndex[char] + 1;
    }
    
    charIndex[char] = right;
    maxLength = Math.max(maxLength, right - left + 1);
  }
  
  return maxLength;
}

Пошаговый разбор примера

// Строка: "abcabcbb"
// Цель: найти самую длинную подстроку без повторений

// Инициализация: left = 0, maxLength = 0, charIndex = {}

// right=0: char=a, charIndex={a:0}, window="a", len=1, max=1
// right=1: char=b, charIndex={a:0,b:1}, window="ab", len=2, max=2
// right=2: char=c, charIndex={a:0,b:1,c:2}, window="abc", len=3, max=3
// right=3: char=a, a в окне (индекс 0), left=1, charIndex={a:3,b:1,c:2}, window="bca", len=3
// right=4: char=b, b в окне (индекс 1), left=2, charIndex={a:3,b:4,c:2}, window="cab", len=3
// right=5: char=c, c в окне (индекс 2), left=3, charIndex={a:3,b:4,c:5}, window="abc", len=3
// right=6: char=b, b в окне (индекс 4), left=5, charIndex={a:3,b:6,c:5}, window="cb", len=2
// right=7: char=b, b в окне (индекс 6), left=7, charIndex={a:3,b:7,c:5}, window="b", len=1

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

Примеры использования

// Базовые примеры
console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
console.log(lengthOfLongestSubstring("bbbbb"));    // 1 ("b")
console.log(lengthOfLongestSubstring("pwwkew"));   // 3 ("wke")
console.log(lengthOfLongestSubstring(""));         // 0

// Дополнительные тесты
console.log(lengthOfLongestSubstring("au"));       // 2 ("au")
console.log(lengthOfLongestSubstring("aab"));      // 2 ("ab")
console.log(lengthOfLongestSubstring("dvdf"));     // 3 ("vdf")
console.log(lengthOfLongestSubstring("abcdefg"));  // 7 ("abcdefg")

Альтернативный подход с Set

function lengthOfLongestSubstring(s) {
  const charSet = new Set();
  let maxLength = 0;
  let left = 0;
  
  for (let right = 0; right < s.length; right++) {
    // Удаляем символы слева, пока не убрём дубликат
    while (charSet.has(s[right])) {
      charSet.delete(s[left]);
      left++;
    }
    
    charSet.add(s[right]);
    maxLength = Math.max(maxLength, right - left + 1);
  }
  
  return maxLength;
}

Визуализация скользящего окна

Строка: "abcabcbb"

Шаг 1: "a" (длина 1)
Шаг 2: "ab" (длина 2)
Шаг 3: "abc" (длина 3) ← максимум
Шаг 4: "bca" (длина 3, дубликат a в позиции 0)
Шаг 5: "cab" (длина 3, дубликат b в позиции 1)
Шаг 6: "abc" (длина 3, дубликат c в позиции 2)
Шаг 7: "cb" (длина 2, дубликат b в позиции 4)
Шаг 8: "b" (длина 1, дубликат b в позиции 6)

Результат: 3

Сравнение подходов

Здесь k — размер алфавита (26 для латиницы, 256 для ASCII, ∞ для Unicode)

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

• charIndex[char] >= left: проверяем, что символ в текущем окне
• left = charIndex[char] + 1: сдвигаем за последнее вхождение
• right - left + 1: длина окна
• Один проход: O(n) временная сложность
• Амортизированная работа: каждый символ посещается максимум дважды

Реальные применения

• Валидация паролей: проверка уникальности символов
• Лексический анализ: поиск токенов без повторений
• Обработка потоков: анализ данных окном фиксированного размера