sc/Все задачи

Минимальное окно подстроки

СложнаяСкользящее окноminimum-window-substring

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

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

Пример 1:

Input: s = "OUZODYXAZV", t = "XYZ"

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

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

Оптимальное решение имеет временную сложность O(n) и пространственную сложность O(k), где n — длина строки s, а k — количество уникальных символов в строке t.

Подсказка 1

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

Подсказка 2

Используйте две хеш-таблицы: одну для подсчета символов в строке t, другую для отслеживания текущего окна.

Подсказка 3

После нахождения валидного окна попробуйте его уменьшить, сдвигая левую границу вправо, пока окно остается валидным.

JavaScript

class Solution {
    // Решение с использованием двух указателей и хеш-таблиц
    minWindow(s, t) {
        if (!s || !t) return "";

        // Создаем хеш-таблицу для подсчета символов в t
        const countT = {};
        for (let c of t) {
            countT[c] = (countT[c] || 0) + 1;
        }

        let left = 0;
        let right = 0;
        let matched = 0;
        const needed = Object.keys(countT).length;
        
        // Хеш-таблица для текущего окна
        const window = {};
        let result = [-1, -1];
        let minLen = Infinity;

        while (right < s.length) {
            // Расширяем окно
            const c = s[right];
            window[c] = (window[c] || 0) + 1;
            
            if (c in countT && window[c] === countT[c]) {
                matched++;
            }

            // Сжимаем окно, если нашли все символы
            while (matched === needed) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    result = [left, right];
                }

                const leftChar = s[left];
                window[leftChar]--;
                
                if (leftChar in countT && window[leftChar] < countT[leftChar]) {
                    matched--;
                }
                
                left++;
            }
            
            right++;
        }

        return minLen === Infinity ? "" : s.slice(result[0], result[1] + 1);
    }
    // Временная сложность: O(n), где n - длина строки s
    // Пространственная сложность: O(k), где k - количество уникальных символов в t

    // Альтернативное решение с использованием фильтрации
    minWindowFiltered(s, t) {
        if (!s || !t) return "";
        
        // Создаем фильтрованный массив с позициями нужных символов
        const filtered = [];
        const countT = {};
        for (let c of t) {
            countT[c] = (countT[c] || 0) + 1;
        }
        
        for (let i = 0; i < s.length; i++) {
            if (s[i] in countT) {
                filtered.push([i, s[i]]);
            }
        }
        
        let left = 0;
        let count = {};
        let formed = 0;
        let result = [-1, -1];
        let minLen = Infinity;
        
        for (let right = 0; right < filtered.length; right++) {
            const char = filtered[right][1];
            count[char] = (count[char] || 0) + 1;
            
            if (count[char] === countT[char]) {
                formed++;
            }
            
            while (formed === Object.keys(countT).length) {
                const currLen = filtered[right][0] - filtered[left][0] + 1;
                if (currLen < minLen) {
                    minLen = currLen;
                    result = [filtered[left][0], filtered[right][0]];
                }
                
                const leftChar = filtered[left][1];
                count[leftChar]--;
                if (count[leftChar] < countT[leftChar]) {
                    formed--;
                }
                left++;
            }
        }
        
        return minLen === Infinity ? "" : s.slice(result[0], result[1] + 1);
    }
    // Временная сложность: O(n), где n - длина строки s
    // Пространственная сложность: O(k), где k - количество уникальных символов в t
}

Python

class Solution:
    # Решение с использованием двух указателей
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""

        # Словарь для подсчета символов в t
        count_t = {}
        for c in t:
            count_t[c] = count_t.get(c, 0) + 1

        required = len(count_t)
        formed = 0
        window = {}
        
        left = 0
        min_len = float('inf')
        result = [-1, -1]

        for right in range(len(s)):
            # Расширяем окно
            char = s[right]
            window[char] = window.get(char, 0) + 1

            if char in count_t and window[char] == count_t[char]:
                formed += 1

            # Сжимаем окно
            while formed == required:
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    result = [left, right]

                left_char = s[left]
                window[left_char] -= 1

                if left_char in count_t and window[left_char] < count_t[left_char]:
                    formed -= 1

                left += 1

        return "" if min_len == float('inf') else s[result[0]:result[1] + 1]

    # Решение с использованием Counter
    def minWindowCounter(self, s: str, t: str) -> str:
        from collections import Counter
        if not s or not t:
            return ""

        target = Counter(t)
        window = Counter()
        required = len(target)
        formed = 0
        
        left = 0
        min_len = float('inf')
        result = [-1, -1]

        for right in range(len(s)):
            char = s[right]
            window[char] += 1

            if char in target and window[char] == target[char]:
                formed += 1

            while formed == required:
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    result = [left, right]

                left_char = s[left]
                window[left_char] -= 1

                if left_char in target and window[left_char] < target[left_char]:
                    formed -= 1

                left += 1

        return "" if min_len == float('inf') else s[result[0]:result[1] + 1]

Java

class Solution {
    // Решение с использованием массива для подсчета
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.isEmpty() || t.isEmpty()) {
            return "";
        }

        // Массив для подсчета символов
        int[] map = new int[128];
        for (char c : t.toCharArray()) {
            map[c]++;
        }

        int left = 0;
        int minLeft = 0;
        int minLen = Integer.MAX_VALUE;
        int count = t.length();

        for (int right = 0; right < s.length(); right++) {
            if (map[s.charAt(right)]-- > 0) {
                count--;
            }

            while (count == 0) {
                if (right - left + 1 < minLen) {
                    minLeft = left;
                    minLen = right - left + 1;
                }

                if (map[s.charAt(left)]++ == 0) {
                    count++;
                }
                left++;
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
    }

    // Решение с использованием HashMap
    public String minWindowMap(String s, String t) {
        if (s == null || t == null || s.isEmpty() || t.isEmpty()) {
            return "";
        }

        Map<Character, Integer> targetMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> windowMap = new HashMap<>();
        int required = targetMap.size();
        int formed = 0;
        int left = 0;
        int[] result = {-1, -1};
        int minLen = Integer.MAX_VALUE;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);

            if (targetMap.containsKey(c) && windowMap.get(c).equals(targetMap.get(c))) {
                formed++;
            }

            while (formed == required) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    result[0] = left;
                    result[1] = right;
                }

                char leftChar = s.charAt(left);
                windowMap.put(leftChar, windowMap.get(leftChar) - 1);

                if (targetMap.containsKey(leftChar) && 
                    windowMap.get(leftChar) < targetMap.get(leftChar)) {
                    formed--;
                }

                left++;
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : 
               s.substring(result[0], result[1] + 1);
    }
}

solution.js · сохранено

Входные данные

"OUZODYXAZV", "XYZ"

Ожидаемый результат

yxaz