LeetCodePython/76_minimum_window_substring.py at main · zhuzhiwei99/LeetCodePython · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
'''
Author: Zhiwei Zhu (zhuzhiwei21@zju.edu.cn)
Date: 2025-09-12 20:19:35
LastEditors: Zhiwei Zhu (zhuzhiwei21@zju.edu.cn)
LastEditTime: 2025-09-12 20:45:31
FilePath: /LeetCodePython/76_minimum_window_substring.py
Description:

Copyright (c) 2025 by Zhiwei Zhu, All Rights Reserved.
'''


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter

        if not t or not s:
            return ""

        dict_t = Counter(t)
        required = len(dict_t)

        l, r = 0, 0
        formed = 0
        window_counts = {}
        ans = float("inf"), None, None

        while r < len(s):
            character = s[r]
            window_counts[character] = window_counts.get(character, 0) + 1

            if character in dict_t and window_counts[character] == dict_t[character]:
                formed += 1

            while l <= r and formed == required:
                character = s[l]

                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)

                window_counts[character] -= 1
                if character in dict_t and window_counts[character] < dict_t[character]:
                    formed -= 1

                l += 1

            r += 1

        return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]


# class Solution:
#     def minWindow(self, s: str, t: str) -> str:
#         s_n = len(s)
#         t_n = len(t)
#         if s_n < t_n:
#             return ""
#         t_count = []
#         t_count_0 = []
#         for i in range(t_n):
#             t_count[t[i]] = t_count.get(t[i], 0) +1
#             t_count_0[t[i]] = 0
#         pre_fix_t_count = [t_count_0]
#         for j in range(s_n):
#             if j > 0:
#                 pre_fix_t_count[j] = pre_fix_t_count[j-1]
#             if s[j] in t:
#                 pre_fix_t_count[j][s[j]] +=1
#         if pre_fix_t_count