LeetCode 76. Minimum Window Substring

November 3, 2024

Last problem for this study set's sliding window problems.

Solution

This is my initial greedy solution. It passes initial test cases, but fails longer inputs.

Copy
1class Solution:
2    def minWindow(self, s: str, t: str) -> str:
3        def containsT(substring):
4            letters = list(t[:])
5            for i in substring:
6                if i in letters:
7                    letters.remove(i)
8            return len(letters) == 0
9
10        n = len(t)
11        m = len(s)
12        windowSize = n
13        while windowSize <= m:
14            for i in range(0, m):
15                substring = s[i:i+windowSize]
16                if containsT(substring):
17                    return substring
18            windowSize += 1
19        return ""

Now to optimize my solution, I plan on stepping through the s string, and tracking how many counts of t letters are found. This should be faster as we are keeping track of letter counts as we go, instead of searching for all letters in the substring for each iteration.

Copy
1class Solution:
2    def minWindow(self, s: str, t: str) -> str:
3        letterCounts = dict()
4        for letter in t:
5            if letter in letterCounts:
6                letterCounts[letter] += 1
7            else:
8                letterCounts[letter] = 1
9        
10        start = 0
11        end = 0
12        windowLength = len(s) + 1
13        minStart = 0
14        lettersRemaining = len(t)
15
16        while end < len(s):
17            if s[end] in letterCounts:
18                if letterCounts[s[end]] > 0:
19                    lettersRemaining -= 1
20                letterCounts[s[end]] -= 1
21            
22            while lettersRemaining == 0:
23                if end - start + 1 < windowLength:
24                    windowLength = end - start + 1
25                    minStart = start
26                if s[start] in letterCounts:
27                    letterCounts[s[start]] += 1
28                    if letterCounts[s[start]] > 0:
29                        lettersRemaining += 1
30                start += 1
31            end += 1
32
33        if windowLength == len(s) + 1:
34            return ""
35        else:
36            return s[minStart:minStart + windowLength]
37
38        return ""

LeetCode 30. Substring with Concatenation of All Words

LeetCode 36. Valid Sudoku