Минимальное окно подстроки: разбор задачи

10 мин чтения

алгоритмы

строки

скользящее окно

хеш-таблицы

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

Задача "Минимальное окно подстроки" позволяет оценить:

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

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

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

Даны две строки s и t. Верните минимальную подстроку строки s, которая содержит все символы строки t, включая дубликаты. Если такой подстроки не существует, верните пустую строку "".

Можно считать, что правильный ответ всегда уникален.

Примеры:

// Первый пример ✅
Input: s = "OUZODYXAZV", t = "XYZ"
Output: "YXAZ"
Объяснение: "YXAZ" - это кратчайшая подстрока, содержащая символы "X", "Y" и "Z" из строки t.

// Второй пример ✅
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Объяснение: "BANC" содержит все символы из "ABC" и является минимальной такой подстрокой.

// Третий пример ❌
Input: s = "a", t = "aa"
Output: ""
Объяснение: "a" не содержит два символа 'a', поэтому возвращается пустая строка.

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

1 <= s.length, t.length <= 10^5
s и t состоят из английских букв в верхнем и нижнем регистрах.

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

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

function minWindow(s, t) {
  const tCount = countChars(t);
  
  let minLength = Infinity;
  let result = "";
  
  // Перебираем все возможные подстроки
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      const subStr = s.substring(i, j + 1);
      const subCount = countChars(subStr);
      
      // Проверяем, содержит ли подстрока все символы из t
      if (containsAll(subCount, tCount)) {
        if (subStr.length < minLength) {
          minLength = subStr.length;
          result = subStr;
        }
      }
    }
  }
  
  return minLength === Infinity ? "" : result;
  
  // Вспомогательные функции
  function countChars(str) {
    const count = {};
    for (const char of str) {
      count[char] = (count[char] || 0) + 1;
    }
    return count;
  }
  
  function containsAll(sourceCount, targetCount) {
    for (const char in targetCount) {
      if (!sourceCount[char] || sourceCount[char] < targetCount[char]) {
        return false;
      }
    }
    return true;
  }
}

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

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

✅ Гарантированно находит минимальную подстроку

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

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

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

function minWindow(s, t) {
  // Если t пустая или длиннее s, решения нет
  if (t.length === 0 || t.length > s.length) return "";
  
  // Подсчитываем частоту символов в t
  const tCount = {};
  for (const char of t) {
    tCount[char] = (tCount[char] || 0) + 1;
  }
  
  let left = 0;               // Левая граница окна
  let right = 0;              // Правая граница окна
  let requiredChars = Object.keys(tCount).length;  // Количество уникальных символов в t
  let formedChars = 0;        // Количество символов, уже найденных в окне
  
  // Счетчик символов в текущем окне
  const windowCount = {};
  
  // Результат: [длина минимального окна, левая граница, правая граница]
  let result = [Infinity, 0, 0];
  
  // Расширяем окно вправо
  while (right < s.length) {
    // Добавляем символ справа в окно
    const rightChar = s[right];
    windowCount[rightChar] = (windowCount[rightChar] || 0) + 1;
    
    // Если добавленный символ необходим и его количество совпадает с требуемым,
    // увеличиваем счетчик сформированных символов
    if (tCount[rightChar] && windowCount[rightChar] === tCount[rightChar]) {
      formedChars++;
    }
    
    // Сужаем окно слева, пока оно содержит все необходимые символы
    while (left <= right && formedChars === requiredChars) {
      // Обновляем результат, если текущее окно меньше
      if (right - left + 1 < result[0]) {
        result = [right - left + 1, left, right];
      }
      
      // Удаляем символ слева из окна
      const leftChar = s[left];
      windowCount[leftChar]--;
      
      // Если удаленный символ необходим и его количество стало меньше требуемого,
      // уменьшаем счетчик сформированных символов
      if (tCount[leftChar] && windowCount[leftChar] < tCount[leftChar]) {
        formedChars--;
      }
      
      left++;
    }
    
    right++;
  }
  
  return result[0] === Infinity ? "" : s.substring(result[1], result[2] + 1);
}

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

✅ Оптимальная временная сложность O(n + m), где n - длина s, m - длина t

✅ Однопроходное решение с алгоритмом скользящего окна

✅ Эффективно обрабатывает повторяющиеся символы

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

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

function minWindow(s, t) {
  // Если t пустая или длиннее s, решения нет
  if (t.length === 0 || t.length > s.length) return "";
  
  // Оптимизация для случая, когда t состоит из одного символа
  if (t.length === 1) {
    const index = s.indexOf(t);
    return index === -1 ? "" : t;
  }
  
  // Подсчитываем частоту символов в t
  const tCount = new Map();
  for (const char of t) {
    tCount.set(char, (tCount.get(char) || 0) + 1);
  }
  
  let left = 0;
  let right = 0;
  let requiredChars = tCount.size;
  let formedChars = 0;
  
  const windowCount = new Map();
  let minLen = Infinity;
  let resultStart = 0;
  
  // Оптимизация: фильтруем строку s, оставляя только символы, которые есть в t
  const filteredPositions = [];
  for (let i = 0; i < s.length; i++) {
    if (tCount.has(s[i])) {
      filteredPositions.push(i);
    }
  }
  
  // Если нет символов из t в s, решения нет
  if (filteredPositions.length < t.length) return "";
  
  // Используем отфильтрованные позиции для скользящего окна
  while (right < filteredPositions.length) {
    const rightPos = filteredPositions[right];
    const rightChar = s[rightPos];
    
    windowCount.set(rightChar, (windowCount.get(rightChar) || 0) + 1);
    
    if (tCount.has(rightChar) && windowCount.get(rightChar) === tCount.get(rightChar)) {
      formedChars++;
    }
    
    while (formedChars === requiredChars) {
      const leftPos = filteredPositions[left];
      const leftChar = s[leftPos];
      
      // Вычисляем длину окна в исходной строке
      const windowLen = rightPos - leftPos + 1;
      
      if (windowLen < minLen) {
        minLen = windowLen;
        resultStart = leftPos;
      }
      
      windowCount.set(leftChar, windowCount.get(leftChar) - 1);
      
      if (tCount.has(leftChar) && windowCount.get(leftChar) < tCount.get(leftChar)) {
        formedChars--;
      }
      
      left++;
    }
    
    right++;
  }
  
  return minLen === Infinity ? "" : s.substring(resultStart, resultStart + minLen);
}

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

✅ Улучшенная производительность за счет предварительной фильтрации

✅ Работает быстрее для случаев, когда t содержит редкие символы

✅ Оптимизации для частых случаев (одиночный символ)

❌ Более сложная реализация с дополнительными проверками

❌ Требует дополнительной памяти для хранения отфильтрованных позиций

Решение 4: Подход с двумя указателями и оптимизированным подсчетом 📊

function minWindow(s, t) {
  // Оптимизация для краевых случаев
  if (!s || !t || s.length < t.length) return "";
  
  // Подсчет символов в t
  const charCount = new Array(128).fill(0);
  for (let i = 0; i < t.length; i++) {
    charCount[t.charCodeAt(i)]++;
  }
  
  let left = 0;
  let right = 0;
  let minStart = 0;
  let minLen = Infinity;
  let requiredChars = t.length;
  
  // Скользящее окно с подсчетом оставшихся требуемых символов
  while (right < s.length) {
    // Если текущий символ нужен (его счетчик > 0), уменьшаем счетчик требуемых символов
    if (charCount[s.charCodeAt(right)] > 0) {
      requiredChars--;
    }
    
    // Уменьшаем счетчик для текущего символа (может стать отрицательным для лишних символов)
    charCount[s.charCodeAt(right)]--;
    right++;
    
    // Когда все требуемые символы найдены, сужаем окно слева
    while (requiredChars === 0) {
      // Обновляем результат, если текущее окно меньше
      if (right - left < minLen) {
        minLen = right - left;
        minStart = left;
      }
      
      // Увеличиваем счетчик для символа, который выходит из окна
      charCount[s.charCodeAt(left)]++;
      
      // Если счетчик стал положительным, это значит,
      // что нам снова требуется этот символ
      if (charCount[s.charCodeAt(left)] > 0) {
        requiredChars++;
      }
      
      left++;
    }
  }
  
  return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
}

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

✅ Очень эффективный подход с минимальным количеством операций

✅ Использует массив для быстрого доступа к счетчикам символов

✅ Отслеживает количество оставшихся требуемых символов вместо сформированных

✅ Пространственная сложность O(1) при использовании фиксированного размера алфавита

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

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

Мы поддерживаем "окно" (подстроку) с помощью двух указателей: left и right.
Постепенно расширяем окно, двигая right вправо, пока не найдем все требуемые символы.
Как только нашли все требуемые символы, пытаемся сузить окно, двигая left вправо, пока окно все еще содержит все требуемые символы.
На каждом шаге сужения обновляем информацию о минимальном окне, если текущее окно меньше.
Продолжаем этот процесс, пока right не достигнет конца строки.

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

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

🤦‍♂️ Неправильный подсчет дубликатов символов
😅 Забывание проверять, что подстрока содержит все требуемые символы
🐛 Ошибки при обновлении счетчиков символов
😕 Неэффективная проверка содержания всех требуемых символов

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

Рассмотрим пример s = "OUZODYXAZV" и t = "XYZ":

Начальное состояние:
s = "OUZODYXAZV", t = "XYZ"
tCount = {"X": 1, "Y": 1, "Z": 1}
left = 0, right = 0, requiredChars = 3, formedChars = 0
windowCount = {}

Шаг 1: right = 0, символ 'O'
windowCount = {"O": 1}
formedChars = 0 (символ 'O' не требуется)
Окно: "O"

Шаг 2: right = 1, символ 'U'
windowCount = {"O": 1, "U": 1}
formedChars = 0
Окно: "OU"

Шаг 3: right = 2, символ 'Z'
windowCount = {"O": 1, "U": 1, "Z": 1}
formedChars = 1 (нашли 'Z')
Окно: "OUZ"

Шаг 4: right = 3, символ 'O'
windowCount = {"O": 2, "U": 1, "Z": 1}
formedChars = 1
Окно: "OUZO"

Шаг 5: right = 4, символ 'D'
windowCount = {"O": 2, "U": 1, "Z": 1, "D": 1}
formedChars = 1
Окно: "OUZOD"

Шаг 6: right = 5, символ 'Y'
windowCount = {"O": 2, "U": 1, "Z": 1, "D": 1, "Y": 1}
formedChars = 2 (нашли 'Y')
Окно: "OUZODY"

Шаг 7: right = 6, символ 'X'
windowCount = {"O": 2, "U": 1, "Z": 1, "D": 1, "Y": 1, "X": 1}
formedChars = 3 (нашли 'X', все символы собраны)
Окно: "OUZODYX" - содержит все требуемые символы

Теперь сужаем окно слева:
left = 0 -> 1: удаляем 'O', formedChars = 3
Окно: "UZODYX"

left = 1 -> 2: удаляем 'U', formedChars = 3
Окно: "ZODYX"

left = 2 -> 3: удаляем 'Z', formedChars = 2 (потеряли 'Z')
Окно: "ODYX" - больше не содержит все требуемые символы

Возвращаемся к расширению окна:
Шаг 8: right = 7, символ 'A'
windowCount = {"O": 1, "U": 0, "Z": 0, "D": 1, "Y": 1, "X": 1, "A": 1}
formedChars = 2
Окно: "ODYXA"

Шаг 9: right = 8, символ 'Z'
windowCount = {"O": 1, "U": 0, "Z": 1, "D": 1, "Y": 1, "X": 1, "A": 1}
formedChars = 3 (нашли 'Z', все символы собраны)
Окно: "ODYXAZ" - содержит все требуемые символы

Снова сужаем окно слева:
left = 3 -> 4: удаляем 'O', formedChars = 3
Окно: "DYXAZ"

left = 4 -> 5: удаляем 'D', formedChars = 3
Окно: "YXAZ" - это минимальное окно!

left = 5 -> 6: удаляем 'Y', formedChars = 2 (потеряли 'Y')
Окно: "XAZ" - больше не содержит все требуемые символы

Продолжаем расширение и сужение, но лучшего результата не находим.
Итоговый результат: "YXAZ"

Оптимизации

Предварительная проверка вхождения всех символов

function minWindow(s, t) {
  // Быстрая проверка: если s короче t, решения нет
  if (s.length < t.length) return "";
  
  // Проверка наличия всех символов t в s (без учета частоты)
  const tChars = new Set(t.split(''));
  const sChars = new Set(s.split(''));
  
  for (const char of tChars) {
    if (!sChars.has(char)) {
      return ""; // Сразу возвращаем пустую строку, если не все символы t есть в s
    }
  }
  
  // Основной алгоритм
  // ...
}

Оптимизация с использованием битовых масок для ASCII-символов

function minWindow(s, t) {
  // Для строк, состоящих только из маленьких латинских букв
  // можно использовать битовые маски
  if (/^[a-z]+$/.test(s) && /^[a-z]+$/.test(t) && t.length <= 26) {
    // Создаем битовую маску для t
    let tMask = 0;
    for (let i = 0; i < t.length; i++) {
      const bit = 1 << (t.charCodeAt(i) - 97);
      tMask |= bit;
    }
    
    // Проверяем, содержатся ли все символы t в s
    let sMask = 0;
    for (let i = 0; i < s.length; i++) {
      const bit = 1 << (s.charCodeAt(i) - 97);
      sMask |= bit;
    }
    
    if ((tMask & sMask) !== tMask) {
      return ""; // Не все символы t есть в s
    }
    
    // Основной алгоритм
    // ...
  }
  
  // Для общего случая
  // ...
}

Прямой подсчет оставшихся символов без хеш-таблицы

function minWindow(s, t) {
  // Для ASCII-символов можно использовать массив вместо хеш-таблицы
  const charCount = new Array(128).fill(0);
  let requiredChars = 0;
  
  // Подсчитываем требуемые символы
  for (let i = 0; i < t.length; i++) {
    charCount[t.charCodeAt(i)]++;
    if (charCount[t.charCodeAt(i)] === 1) {
      requiredChars++; // Увеличиваем счетчик только для уникальных символов
    }
  }
  
  let left = 0;
  let right = 0;
  let formedChars = 0;
  let minLen = Infinity;
  let resultStart = 0;
  
  while (right < s.length) {
    const rightChar = s.charCodeAt(right);
    
    // Уменьшаем счетчик для текущего символа
    charCount[rightChar]--;
    
    // Если счетчик стал равен 0, значит, мы нашли требуемое количество этого символа
    if (charCount[rightChar] === 0 && charCount[rightChar] > -1) {
      formedChars++;
    }
    
    // Сужаем окно, когда нашли все требуемые символы
    while (formedChars === requiredChars) {
      // Обновляем результат
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        resultStart = left;
      }
      
      const leftChar = s.charCodeAt(left);
      
      // Увеличиваем счетчик для символа, который выходит из окна
      charCount[leftChar]++;
      
      // Если счетчик стал положительным, значит, этот символ снова требуется
      if (charCount[leftChar] === 1 && t.indexOf(s[left]) !== -1) {
        formedChars--;
      }
      
      left++;
    }
    
    right++;
  }
  
  return minLen === Infinity ? "" : s.substring(resultStart, resultStart + minLen);
}

Заключение

При решении задачи "Минимальное окно подстроки" важно помнить:

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

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

AI Помощник BETA

Авторизуйтесь, чтобы задать вопрос

Для использования AI-помощника необходимо авторизоваться

Примеры вопросов:

Разработчик, готов покорять новые вершины?

Мы создали идеальную платформу для подготовки к собеседованиям. Никакого стресса – только уверенность в своих силах!

📱Стартовый бонус

Мгновенный доступ к платформе

14 дней бесплатного использования

💫Уникальный контент

Задачи на русском языке с детальным разбором

Специально для российских компаний

🔥Умный бот

Уведомления о новых задачах

Доступ к материалам в любое время

🎯Начать подготовку прямо сейчас!

ℹ️Никакого спама – только полезный контент для твоего роста!

Практика