76. Minimum Window Substring

Задача

Даны строки s и t. Верните минимальную подстроку s, содержащую все символы t (с учётом кратности). Если её нет — пустую строку.

Примеры

Пример 1

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Пояснение

Минимальное окно “BANC” содержит ‘A’, ‘B’ и ‘C’ из строки t.

Пример 2

Input: s = "a", t = "a"
Output: "a"

Пояснение

Вся строка s является минимальным окном.

Пример 3

Input: s = "a", t = "aa"
Output: ""

Пояснение

Обе ‘a’ из t должны попасть в окно, но в s только одна ‘a’ — возвращаем пустую строку.

Решение

Решение

/**
 * Сложность по времени (Time Complexity): O(s + t)
 *    1. Мы проходим по t один раз, чтобы заполнить карту частот.
 *    2. Мы проходим по s с помощью правого указателя (right).
 *    3. Левый указатель (left) тоже проходит по s, но не более одного раза для каждого символа.
 *    Итого: O(2 * s + t) -> O(s + t).
 *
 * Сложность по памяти (Space Complexity): O(1) (или O(m))
 *    Мы храним Map, но так как количество уникальных символов в алфавите ограничено
 *    (максимум 52 для a-z и A-Z, или 128 для ASCII), размер Map не растет бесконечно с ростом s.
 */
var minWindow = function(s, t) {
    if (t.length > s.length) return "";
 
    // Словарь частот того, что нам НУЖНО найти
    const map = new Map();
    for (const char of t) {
        map.set(char, (map.get(char) || 0) + 1);
    }
 
    let left = 0;
    let right = 0;
 
    // Сколько уникальных "полезных" символов нам осталось собрать.
    // Когда count станет равен 0, значит окно валидно.
    let count = t.length;
 
    // Для отслеживания минимального окна
    let minLen = Infinity;
    let minStart = 0;
 
    while (right < s.length) {
        const char = s[right];
 
        // Если текущий символ есть в t, уменьшаем его счетчик в Map
        if (map.has(char)) {
            // Если счетчик был > 0, значит мы нашли полезный символ, уменьшаем общий count
            if (map.get(char) > 0) {
                count--;
            }
            // Уменьшаем значение в Map. Оно может уйти в минус (это значит у нас избыток этого символа)
            map.set(char, map.get(char) - 1);
        }
 
        // Как только собрали все нужные символы (count === 0), начинаем сжимать окно слева
        while (count === 0) {
            // Обновляем минимальный результат, если текущее окно меньше
            const currentLen = right - left + 1;
            if (currentLen < minLen) {
                minLen = currentLen;
                minStart = left;
            }
 
            const leftChar = s[left];
 
            // Если уходящий символ был в t, нужно обновить Map и count
            if (map.has(leftChar)) {
                map.set(leftChar, map.get(leftChar) + 1);
 
                // Если после возвращения символа его стало больше 0,
                // значит окно перестало быть валидным (нам снова нужен этот символ)
                if (map.get(leftChar) > 0) {
                    count++;
                }
            }
 
            left++;
        }
 
        right++;
    }
 
    return minLen === Infinity ? "" : s.substr(minStart, minLen);
};