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

Почему эта задача важна?

Задача на поиск самой длинной подстроки без повторяющихся символов позволяет оценить:

• 🧠 Умение работать с алгоритмом скользящего окна
• ⚡ Навыки оптимизации решения от квадратичной до линейной сложности
• 🎯 Эффективное использование хеш-таблиц и множеств
• 🔍 Способность обрабатывать повторяющиеся элементы в последовательностях

Постановка задачи

Формулировка:

Дана строка s, найдите длину самой длинной подстроки без повторяющихся символов. Подстрока - это непрерывная последовательность символов внутри строки.

Примеры:

// Первый пример ✅
Input: s = "abcabcbb"
Output: 3
Объяснение: Самая длинная подстрока без повторов - "abc", длина = 3.

// Второй пример ✅
Input: s = "bbbbb"
Output: 1
Объяснение: Самая длинная подстрока без повторов - "b", длина = 1.

// Третий пример ✅
Input: s = "pwwkew"
Output: 3
Объяснение: Самая длинная подстрока без повторов - "wke", длина = 3.
Обратите внимание, что ответом должна быть длина подстроки, а не последовательности.
"pwke" - это последовательность, а не подстрока.

Ограничения:

• 0 <= s.length <= 5 * 10^4
• s состоит из английских букв, цифр, символов и пробелов.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Подходы к решению

Решение 1: Наивный подход (перебор всех подстрок) 🔍

function lengthOfLongestSubstring(s) {
  let maxLength = 0;
  
  for (let i = 0; i < s.length; i++) {
    // Множество для отслеживания символов в текущей подстроке
    const charSet = new Set();
    
    for (let j = i; j < s.length; j++) {
      // Если символ уже встречался, прерываем проверку текущей подстроки
      if (charSet.has(s[j])) {
        break;
      }
      
      // Добавляем символ в множество и обновляем максимальную длину
      charSet.add(s[j]);
      maxLength = Math.max(maxLength, j - i + 1);
    }
  }
  
  return maxLength;
}

Анализ решения:

✅ Простая реализация и понятная логика

✅ Гарантированно находит правильный ответ

❌ Временная сложность O(n²), где n - длина строки

❌ Неэффективен для длинных строк

Решение 2: Скользящее окно с использованием множества (оптимальное решение) 🚀

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;
}

Характеристики:

✅ Оптимальная временная сложность O(n)

✅ Пространственная сложность O(min(m, n)), где m - размер алфавита

✅ Использует технику скользящего окна для эффективного перебора

✅ Один проход по строке

Решение 3: Оптимизированное скользящее окно с хеш-таблицей 🔧

function lengthOfLongestSubstring(s) {
  // Хеш-таблица для хранения индексов символов
  const lastSeen = new Map();
  let maxLength = 0;
  
  // Левая граница скользящего окна
  let left = 0;
  
  for (let right = 0; right < s.length; right++) {
    const currentChar = s[right];
    
    // Если символ уже встречался и находится в текущем окне,
    // обновляем левую границу
    if (lastSeen.has(currentChar) && lastSeen.get(currentChar) >= left) {
      left = lastSeen.get(currentChar) + 1;
    } else {
      // Обновляем максимальную длину
      maxLength = Math.max(maxLength, right - left + 1);
    }
    
    // Обновляем индекс последнего появления символа
    lastSeen.set(currentChar, right);
  }
  
  return maxLength;
}

Преимущества и недостатки:

✅ Временная сложность O(n)

✅ Не требует дополнительного цикла для удаления символов

✅ Более эффективное управление скользящим окном

❌ Немного сложнее для понимания

Решение 4: Использование массива для ASCII-символов (оптимизация по памяти) 📊

function lengthOfLongestSubstring(s) {
  // Для ASCII-символов используем массив вместо хеш-таблицы
  // Инициализируем -1, чтобы показать, что символ еще не встречался
  const lastSeen = new Array(128).fill(-1);
  
  let maxLength = 0;
  let left = 0;
  
  for (let right = 0; right < s.length; right++) {
    const charCode = s.charCodeAt(right);
    
    // Если символ уже встречался и находится в текущем окне
    if (lastSeen[charCode] >= left) {
      left = lastSeen[charCode] + 1;
    } else {
      maxLength = Math.max(maxLength, right - left + 1);
    }
    
    // Обновляем индекс последнего появления символа
    lastSeen[charCode] = right;
  }
  
  return maxLength;
}

Особенности:

✅ Временная сложность O(n)

✅ Более эффективное использование памяти для ASCII-символов

✅ Быстрый доступ к элементам массива по индексу

❌ Работает только с ASCII-символами (для Unicode требуется хеш-таблица)

Почему работает алгоритм скользящего окна?

Алгоритм скользящего окна основан на следующей идее:

1. Мы поддерживаем "окно" символов, которое содержит только уникальные символы.
2. Правая граница окна расширяется с каждой итерацией, добавляя новый символ.
3. Если добавляемый символ уже есть в окне, мы сдвигаем левую границу вправо до тех пор, пока не удалим повторяющийся символ.
4. На каждом шаге мы обновляем максимальную длину, если текущее окно больше.

Этот подход позволяет избежать повторного перебора всех подстрок и достичь линейной сложности.

Рекомендации по решению 💡

1. Выбор метода решения:

   • 🚀 Скользящее окно с хеш-таблицей/множеством - оптимальный выбор
   • 📝 Для ASCII-символов можно использовать массив для экономии памяти
   • 🧮 Избегайте наивного перебора всех подстрок

2. Важные моменты:

   • 📝 Правильная обработка повторяющихся символов
   • 🔄 Корректное обновление левой границы окна
   • 📊 Регулярное обновление максимальной длины

Распространённые ошибки

1. 🤦‍♂️ Неправильная обработка случая, когда повторяющийся символ находится вне текущего окна
2. 😅 Забывание обновить максимальную длину после каждого расширения окна
3. 🐛 Путаница между подстрокой (непрерывная последовательность) и подпоследовательностью

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

Рассмотрим пример строки "abcabcbb":

Начальное состояние:
s = "abcabcbb", left = 0, right = 0, maxLength = 0, charSet = {}

Шаг 1: right = 0, символ 'a'
Добавляем 'a' в charSet = {'a'}
Окно: "a", длина = 1, maxLength = 1

Шаг 2: right = 1, символ 'b'
Добавляем 'b' в charSet = {'a', 'b'}
Окно: "ab", длина = 2, maxLength = 2

Шаг 3: right = 2, символ 'c'
Добавляем 'c' в charSet = {'a', 'b', 'c'}
Окно: "abc", длина = 3, maxLength = 3

Шаг 4: right = 3, символ 'a' (повтор)
'a' уже в charSet, поэтому удаляем символы слева до первого 'a'
Удаляем 'a', left = 1
charSet = {'b', 'c', 'a'}
Окно: "bca", длина = 3, maxLength = 3

Шаг 5: right = 4, символ 'b' (повтор)
'b' уже в charSet, поэтому удаляем символы слева до первого 'b'
Удаляем 'b', left = 2
charSet = {'c', 'a', 'b'}
Окно: "cab", длина = 3, maxLength = 3

Шаг 6: right = 5, символ 'c' (повтор)
'c' уже в charSet, поэтому удаляем символы слева до первого 'c'
Удаляем 'c', left = 3
charSet = {'a', 'b', 'c'}
Окно: "abc", длина = 3, maxLength = 3

Шаг 7: right = 6, символ 'b' (повтор)
'b' уже в charSet, поэтому удаляем символы слева до первого 'b'
Удаляем 'a', left = 4
Удаляем 'b', left = 5
charSet = {'c', 'b'}
Окно: "cb", длина = 2, maxLength = 3

Шаг 8: right = 7, символ 'b' (повтор)
'b' уже в charSet, поэтому удаляем символы слева до первого 'b'
Удаляем 'c', left = 6
Удаляем 'b', left = 7
charSet = {'b'}
Окно: "b", длина = 1, maxLength = 3

Итоговый результат: maxLength = 3

Оптимизации

Раннее обнаружение оптимального решения

function lengthOfLongestSubstring(s) {
  // Если строка пуста или имеет длину 1, результат очевиден
  if (s.length <= 1) return s.length;
  
  const charMap = new Map();
  let maxLength = 0;
  let left = 0;
  
  for (let right = 0; right < s.length; right++) {
    if (charMap.has(s[right])) {
      left = Math.max(left, charMap.get(s[right]) + 1);
    }
    
    charMap.set(s[right], right);
    maxLength = Math.max(maxLength, right - left + 1);
    
    // Если максимальная длина равна оставшейся части строки,
    // дальнейшее улучшение невозможно
    if (maxLength >= s.length - left) {
      break;
    }
  }
  
  return maxLength;
}

Оптимизация для случая, когда все символы уникальны

function lengthOfLongestSubstring(s) {
  // Быстрая проверка для случая, когда все символы уникальны
  const uniqueChars = new Set(s);
  if (uniqueChars.size === s.length) {
    return s.length;
  }
  
  // Основной алгоритм для общего случая
  const charMap = new Map();
  let maxLength = 0;
  let left = 0;
  
  for (let right = 0; right < s.length; right++) {
    if (charMap.has(s[right]) && charMap.get(s[right]) >= left) {
      left = charMap.get(s[right]) + 1;
    } else {
      maxLength = Math.max(maxLength, right - left + 1);
    }
    
    charMap.set(s[right], right);
  }
  
  return maxLength;
}

Заключение

При решении задачи "Самая длинная подстрока без повторяющихся символов" важно помнить:

• 🤹‍♂️ Техника скользящего окна - оптимальный подход для поиска подстрок с определенными свойствами
• 📊 Хеш-таблицы/множества позволяют эффективно отслеживать уникальность символов
• 🧠 Правильное управление границами окна - ключ к эффективному решению

Эта задача демонстрирует важность понимания алгоритма скользящего окна и его применения для оптимизации поиска в строках и последовательностях. Она также показывает, как использование подходящих структур данных позволяет значительно улучшить производительность. 🌟