I am going to use two examples related with Sliding window algorithm to explain this concept.

Find All Anagrams in a String:

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.

Input:
s: “cbaebabacd” p: “abc”
Output:
[0, 6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        lp = len(p)
        cp = collections.Counter(p)
        count = lp
        ans = []
        for i in xrange(0, len(s)):
            if cp[s[i]] >= 1:
                count -= 1
            cp[s[i]] -= 1
            if i >= lp:
                if cp[s[i-lp]] >= 0:
                    count += 1
                cp[s[i-lp]] += 1
            if count == 0:
                ans.append(i-lp+1)
        return ans

Firstly, we need to use collections.Counter(p) to calculate the frequency of letter in string p. Then “i” can be considered as the right side of the “window”. “count” means the number of letters to complete the substring.
when cp[s[i]] >= 1, the current letter can consist this substring, so we are closer to the final substring, and we can decrease count(count -= 1).

The important thing is cp[s[i]] should minus one as well, because in this substring, we have used one in the cp. (If the letter does not exist in the cp, the value of that letter should be <0).

Then when i >= lp, we increase i each time, that means we will add one to the previous substring and pop the first element of the previous substring. There will be some possibility that the letter we pop out is the one we need. So when this happen, we need to count += 1, because we pop out the first element. We need to add that back to the cp which is cp[s[i-ip]].

Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.
Note:
If there is no such window in S that covers all characters in T, return the empty string “”.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
Here is the Python code of this problem:

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

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        if len(t)>len(s):
            return ""
        lt = len(t)
        count = lt
        ct = collections.Counter(t)
        left = 0
        right = 0
        minLength = sys.maxint
        notfound = 1
        ansleft = 0
        ansright = 0
        for i in xrange(0, len(s)):
            if ct[s[i]] > 0:
                count -= 1
            ct[s[i]] -= 1
            while count == 0:
                right = i
                notfound = 0
                if right -left < minLength:
                    minLength = right-left
                    ansleft = left
                    ansright = right
                if ct[s[left]] == 0:
                    count += 1
                ct[s[left]] += 1
                left += 1
        if notfound == 1:
            return ""
        return s[ansleft:ansright+1]

The idea I need to highlight is Line 30 to Line 33, when ct[s[left]] == 0, count should add one. The reason is when we pop out this number, the remainder should be 1, and just because of this action, the substring is not complete now, and we need to search another one to fill in this hole.

Comments: