[Leetcode] Two Pointers in Sliding Window

Posted on | In , , |

Intro

Sliding Window for Substring problem Template:
https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/92007/Sliding-Window-algorithm-template-to-solve-all-the-Leetcode-substring-search-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
def slidingWindow(s, p):
    res = []
    if (len(p) > len(s)): return res
    # dictionary to save pattern
    d = {}
    for ch in p:
        if ch in d:
            d[ch] += 1
        else:
            d[ch] = 1
    # Use cnt to check whether match the target string
    cnt = len(d)

    # Two pointers: left, right
    left = right = 0
    while right < len(s):
        cur = s[right]
        if cur in d:
            d[cur] -= 1
            if d[cur] == 0:
                cnt -= 1 # remove one character
        right += 1

        # Increase left pointer to make it invalid/valid again
        while cnt == 0: # When all characters in p are found in s[left: right + 1]
            l = s[left]
            if l in d:
                d[l] += 1 # move left forward
                if d[l] > 0:
                    cnt += 1
            # save the result if find a target
            left += 1
    return res

Substring problem

438. Find All Anagrams in a String

Leetcode: https://leetcode.com/problems/find-all-anagrams-in-a-string/

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
def findAnagrams(self, s: str, p: str) -> List[int]:
    if len(p) > len(s): return []
    left = right = 0
    d = {}
    res = []
    for ch in p:
        if ch in d:
            d[ch] += 1
        else:
            d[ch] = 1
    cnt = len(d)
    
    while right < len(s):
        cur = s[right]
        if cur in p:
            d[cur] -= 1
            if d[cur] == 0:
                cnt -= 1
        right += 1
        
        while cnt == 0:
            l = s[left]
            if l in d:
                d[l] += 1
                if d[l] > 0:
                    cnt += 1
            if right - left == len(p):
                res.append(left)
            left += 1
    return res

340. Longest Substring with At Most K Distinct Characters

Leetcode: https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
    d = collections.defaultdict(int)
    res = 0
    left = right = 0
    while right < len(s):
        cur = s[right]
        d[cur] += 1
        
        while left <= right and len(d) > k:
            d[s[left]] -= 1
            if d[s[left]] == 0:
                del d[s[left]]
            left += 1
        if len(d) <= k:
            res = max(res, right - left + 1)
        right += 1
    return res

76. Minimum Window Substring

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

Solution: https://www.youtube.com/watch?v=9qFR2WQGqkU

1
2
3
4
5
6
7
find A B C
in           A D O B E C O D E B A N C
slow         ^
fast         ^
matchCount
minLength
index

matchCount: record how many keys in wordDict are FULLY matched
minLength: record the minimum length of matched Substring
index: record the head index of the minimum substring

  • Use slow and fast two pointers to update window
  • Construct a wordDict with HashMap
  • Forward the fast pointer to check if any character belongs to the dict keys
    • char ch = s.charAt(fast) check if the Character at fast is in the wordDict
      • if not: forward
      • if in the wordDict, update the wordDict count (needMatch - 1), update matchCount++
      • While all characters in wordDict are matched:
        • find the valid substring, record index, minLength
        • move slow pointer to left, check the leftmost character
        • if leftmost character not in the wordDict, doesn’t matter, move forward
        • else if leftmost character in the wordDict, update the wordDict count (needMatch + 1)
        • if leftmost character has increased from 0 to 1 in wordDict, which means matched character reduced by 1
          • matchCount--
  • if minLength is still Integer.MAX_VALUE: not matched: return “”, else return s.substring(index, index + minLength)

[Caption]:

how to construct map wordDict function

1
2
3
4
5
6
7
8
9
10
11
12
private Map<Character, Integer> constructWordDict(String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (char ch : t.toCharArray()) {
            Integer count = map.get(ch);
            if (count == null) {
                map.put(ch, 1);
            } else {
                map.put(ch, count + 1);
            }
        }
        return map;
    }

3. Longest Substring Without Repeating Characters[M]

Leetcode: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

Solution

  1. Use a HashSet to store unique values
  2. Use the window problem template
  3. Solution: https://leetcode.com/articles/longest-substring-without-repeating-characters/
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
const lengthOfLongestSubstringTwoDistinct = (s) => {
    if (!s) {
        return 0;
    }
    
    let dict = {};
    let cnt = 0; // total in dict
    let max = 0;
    let head = 0;
    let tail = 0;
    
    // keep track of the first entry in the dict
    // loop through s
    while (tail < s.length) {
        // Put chars into map
        let temp = dict[s.charAt(tail)];
        if (temp) {
            dict[s.charAt(tail)] += 1;
        } else {
            dict[s.charAt(tail)] = 1;
        }
        cnt += 1;
        while (Object.keys(dict).length > 2) { // While not match, update dict
            // forward head, make window small, and update dict
            dict[s.charAt(head)] -= 1;
            if (dict[s.charAt(head)] === 0) {
                delete dict[s.charAt(head)];
            }
            head++; 
            cnt -= 1;
        }
        max = Math.max(max, cnt);
        tail += 1;
    }
    return max;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def lengthOfLongestSubstring(self, s: str) -> int:
    if not s:
        return 0
    l = r = 0
    res = 0
    visited = set()
    while r < len(s):
        if s[r] in visited:
            while s[l] != s[r]:
                visited.remove(s[l])
                l += 1
            visited.remove(s[l])
            l += 1
        visited.add(s[r])
        res = max(res, r - l + 1)
        r += 1
    return res

159. Longest Substring with At Most Two Distinct Characters

Leetcode: https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/description/

Solution

  1. Use Hashtable to keep track of counts of characters
  2. Use the window problem template
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
    d = collections.defaultdict(int)
    res = 0
    left = right = 0
    cnt = 0
    while right < len(s):
        cur = s[right]
        d[cur] += 1
            
        while len(d) > 2:
            d[s[left]] -= 1
            if d[s[left]] == 0:
                d.pop(s[left], None)
            left += 1
            
        if len(d) <= 2:
            res = max(res, right - left + 1)
        right += 1
    return res

30. Substring with Concatenation of All Words

Leetcode: https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/

Solution: https://www.youtube.com/watch?v=L6NLra-rZoU

(The description of this problem is not consistent with its test cases in terms of if the words’ length are the same. This solution is based on the assumption that all words’ lengths are the same)

1
2
3
4
5
6
7
find ["foo","bar"]
s           "dat bar foo the foo bar man"
slow                                 ^
fast                             ^
wordDict: {"foo":1, "bar":1}
matchCount:  0
heads: [         3,          12,]

fast: fast pointer
slow: slow pointer
matchCount: how many string items left to be matched
heads: keep track of the heads
step: word length
wordDict: Map that keep track of how many words left to be matched

Solution

  1. Get the wordDict
  2. Forward the fast pointer at a pace of step
    1. If word at the fast pointer not match in the wordDict
      1. Discard all the steps and restore wordDict and matchCount, continue
    2. Else if the word matched in the wordDict
      1. update the wordDict value
      2. If the word is fully matched, matchCount++
      3. If all words are fully matched
      4. record slow index in the heads
      5. move forward slow index
      6. Restore wordDict and matchCount, continue

904. Fruit Into Baskets

Leetcode: https://leetcode.com/problems/fruit-into-baskets/

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
def totalFruit(self, tree):
    """
    :type tree: List[int]
    :rtype: int
    """
    # Find a start point that can maximize the step within two types
    # [3,3,3,1,2,1,1,2,3,3,4]
    #  0 1 2 3 4 5 6 7 8 9 10
    # index is important
    # unique count -> dict
    res = 0
    left = 0
    right = 0
    basket = {}
    while left <= right < len(tree):
        if tree[right] in basket:
            basket[tree[right]] += 1
        else:
            basket[tree[right]] = 1
        right += 1
        while len(basket) > 2:
            basket[tree[left]] -= 1
            if basket[tree[left]] == 0:
                basket.pop(tree[left], None)
            left += 1
        res = max(res, right - left)
    return res

Subarray Problems

209. Minimum Size Subarray Sum

Leetcode: https://leetcode.com/problems/minimum-size-subarray-sum/description/

Window problem template:

1
2
3
4
5
6
7
While(tail < nums.length):
  add num[tail] -> window
  while not match:
    head++ {move window}
    if match:
      update result
return result

Note:

  1. Remember to return 0 when no reslut found
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
    l = r = 0
    res = len(nums) + 1
    sm = 0
    while r < len(nums):
        sm += nums[r]
        while l <= r and sm >= s:
            res = min(res, r - l + 1)
            sm -= nums[l]
            l += 1
        r += 1
    if res == len(nums) + 1:
        return 0
    return res

Binary Search Approach: Ologn

1
2
3
4
5
6
7
8
9
10
11
12
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
    res = len(nums) + 1
    if not nums:
        return 0
    sums = [0] + [nums[0]]
    for i in range(1, len(nums)):
        sums.append(sums[-1] + nums[i])
    for i in range(len(nums)):
        index = bisect_left(sums, sums[i] + s, i, len(sums))
        if index < len(sums):
            res = min(res, index - i)
    return res if res != len(nums) + 1 else 0

713. Subarray Product Less Than K

Leetcode: https://leetcode.com/problems/subarray-product-less-than-k/

Note:

  1. The condition for the while loop is l <= r, if num itself is larger than the target, then l = r + 1, then cnt will be added 0.

  2. For every new number r introduces, the count will increase r - l + 1
    for window (5, 2), when 6 is introduced, it add 3 new subarray:

    1
    2
    3
        (6)
      (2,6)
    (5,2,6)

  3. Use l <= r rather than l < r since we can count one element as a single subarray

1
2
3
4
5
6
7
8
9
10
11
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
    l = r = cnt = 0
    product = 1
    while r < len(nums):
        product *= nums[r]
        while product >= k and l <= r: # l <= r
            product /= nums[l]
            l += 1
        cnt += r - l + 1
        r += 1
    return cnt

992. Subarrays with K Different Integers

Leetcode: https://leetcode.com/problems/subarrays-with-k-different-integers/

Note:

  1. Number of subarrays With exact K = Number of subarrays with at most K - Number of subarrays with at most K - 1
  2. For each new element r introduces, we increase l - r + 1.
    1
    2
    3
    4
    1, 2, 2 is valid, we introduce 2
    1, 2, 2, 2
       2, 2, 2
          2, 2 will all be valid since it's AT MOST K, not exact K
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
    def atMost(k):
        l = r = cnt = 0
        counts = [0] * (len(A) + 1)
        s = set()
        while r < len(A):
            counts[A[r]] += 1
            s.add(A[r])
            if len(s) > k:
                while l <= r and len(s) > k:
                    counts[A[l]] -= 1
                    if counts[A[l]] == 0:
                        s.remove(A[l])
                    l += 1
            cnt += r - l + 1
            r += 1
        return cnt
    return atMost(K) - atMost(K - 1)

487. Max Consecutive Ones II

Leetcode: https://leetcode.com/problems/max-consecutive-ones-ii/

Note:
Set a zero value for 0, once it’s below 1, we move l pointer forward.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
    l, r = 0, 0
    zero = 1
    res = 0
    while r < len(nums):
        if nums[r] == 0:
            while zero < 1:
                if nums[l] == 0:
                    zero += 1
                l += 1
            zero -= 1
        res = max(res, r - l + 1)
        r += 1
    return res

1004. Max Consecutive Ones III

Leetcode: https://leetcode.com/problems/max-consecutive-ones-iii/

Note: Same as the problem above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def longestOnes(self, A: List[int], K: int) -> int:
    l, r = 0, 0
    zero = K
    res = 0
    while r < len(A):
        if A[r] != 1:
            while zero == 0:
                if A[l] == 0:
                    zero += 1
                l += 1
            zero -= 1
        res = max(res, r - l + 1)
        r += 1
    return res