Intruction

The Sliding Window algorithm is a method for finding a subset of elements that satisfy a certain condition in issues.

Slide_Window

The Sliding Window Algorithm is a specific technique used in computer science and programming to efficiently solve problems that involve arrays, strings, or other data structures by maintaining a “window” of elements within a certain range and moving that window through the data to perform operations or calculations.

Example:

76. Minimum Window Substring

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 "".

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

  • 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.

Solution

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

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        m,n=len(s),len(t)
        mp = defaultdict(int)  #Used to store the number of characters in t

        ans = float('inf')
        start = 0

        for x in t:
            mp[x]+=1 #Increase the count of each character in t

        count = len(mp)

        i = 0
        j = 0

        while j < len(s):
            mp[s[j]]-=1 #decrease the count of each character in s
            if mp[s[j]] == 0:   #means one kind of characters in t is included in the window
                count -= 1      

            if count == 0:  #Means the window already contain all the characters in t
                while count == 0:
                    if ans > j - i + 1: # check the smallest window
                        ans = j - i + 1  
                        start = i
                    mp[s[i]] +=1 
                    if mp[s[i]] > 0:     #calculate the next window
                        count += 1

                    i += 1
            j+=1
        if ans != float('inf'):
            return s[start:start + ans]
        else:
            return ""