76. Minimum Window Substring

Problem

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

A substring is a contiguous non-empty sequence of characters within a string.

The testcases will be generated such that the answer is unique.

https://leetcode.com/problems/minimum-window-substring/

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes ‘A’, ‘B’, and ‘C’ from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a’s from t must be included in the window.
Since the largest window of s only has one ‘a’, return empty string.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 10^5
s and t consist of uppercase and lowercase English letters.

Test Cases

1 2	class Solution: def minWindow(self, s: str, t: str) -> str:

solution_test.py

import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('s, t, expected', [
    ("ADOBECODEBANC", "ABC", "BANC"),
    ("a", "a", "a"),
    ("a", "aa", ""),
])
class Test:
    def test_solution(self, s, t, expected):
        sol = Solution()
        assert sol.minWindow(s, t) == expected

    def test_solution2(self, s, t, expected):
        sol = Solution2()
        assert sol.minWindow(s, t) == expected

Thoughts

设当前窗口的左右边界分别是 i 和 j，如果当前子串已经包含 t 中所有字符则右移 i，否则右移 j。

事先统计出 t 中出现的所有字符及数量，在移动 i、j 的时候同步更新子串中的字符种类及数量。

设 t 中有 k 种不同的字符，则时间复杂度是 O(n+km)，空间复杂度 O(k)。

当 k 比较大时，每移动一次 i 或 j 都比一次窗口内各种字符的数量与 t 是否一致就比较浪费，比如移入或移出的字符并不在 t 内，或者移出了一个数量已经超出需求很多的字符，或者移入了一个需要的字符但还有很多其他也需要的字符。要把每次移动 i 或 j 时的处理时间降到 O(1)。

可以再维护一个字符的集合，表示窗口内缺少的字符。在移动 i、j 并更新窗口内字符数量时，直接判定当前字符是否还需要，并相应地加入或移出集合，这样每次判定就只需要常数时间。

如果控制好字符加入和移出集合的时机，确保不会重复加入和移出不存在的字符，那就不需要真的放一个集合，只需要记录还缺少的字符数量，可以省掉集合的存储空间和相关操作的时长。

整体的时间复杂度是 O(n+m)，空间复杂度 O(k)。

Code

👇 单一循环体

solution.py

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        m = len(s)
        if m < len(t):
            return ''

        needs: dict[str, int] = {} # character: number of this character needed.
        for c in t:
            needs[c] = needs.get(c, 0) + 1
        miss = len(needs)

        min_i = min_len = 0
        i = j = 0
        while not (miss and j == m):
            if miss:
                if (c := s[j]) in needs:
                    needs[c] -= 1
                    if needs[c] == 0:
                        miss -= 1
                j += 1
            else:
                if (c := s[i]) in needs:
                    needs[c] += 1
                    if needs[c] == 1:
                        miss += 1
                        if (curr_len := j - i) < min_len or min_len == 0:
                            min_i = i
                            min_len = curr_len
                i += 1

        return s[min_i:min_i+min_len]

👇 循环套循环

solution2.py

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        m = len(s)
        if m < len(t):
            return ''

        needs: dict[str, int] = {} # character: number of this character needed.
        for c in t:
            needs[c] = needs.get(c, 0) + 1
        miss = len(needs)

        min_i = min_len = 0
        i = j = 0
        while True:
            while miss and j < m:
                if (c := s[j]) in needs:
                    needs[c] -= 1
                    if needs[c] == 0:
                        miss -= 1
                j += 1

            if miss:
                break

            while not miss:
                if (c := s[i]) in needs:
                    needs[c] += 1
                    if needs[c] == 1:
                        miss += 1
                i += 1

            if (curr_len := j - i + 1) < min_len or min_len == 0:
                min_len = curr_len
                min_i = i - 1

        return s[min_i:min_i+min_len]

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。