Algorithm - Two Pointers (1) - Sliding Window

Two pointers problem set (1) - Sliding Window

• 76.Minimum Window Substring
• 567.Permutation in String
• 438.Find All Anagrams in a String
• 3.Longest Substring Without Repeating Characters
• 239.Sliding Window Maximum

Template

# find string t in string s
from collection import Counter, defaultdict
def sliding_window(s, t):
	need = Counter(t)
	valid = 0
	left = right = 0

	while right < len(s):
		c = s[right]
		right += 1

		# do something
		...

		while window needs shrink:
			d = s[left]
			left += 1
			# do something
			...

76. Minimum Window Substring

1. Extend right pointer until all characters found
2. Log smallest window
3. Shrink left pointer until found the next valid window

from collections import Counter, defaultdict
def minWindow(self, s: str, t: str) -> str:
    needs = dict(Counter(t))
    left = right = 0
    counter = len(t)
    min_len = float('inf')
    res = ''
    
    # search [left. right)
    while right < len(s):
        
        c = s[right]
        if c in needs:
        	# is a valid character
        	needs[c] -= 1
            counter -= needs[c] >= 0

        right += 1
        
        while not counter:
            
            # update res
            if (right - left) < min_len:
                min_len = right - left
                res = s[left: right]
            
            c = s[left]
            if c in needs:
                needs[c] += 1
                counter += needs[c] > 0
            
            left += 1
            
    return res

567. Permutation in String

True criteria is len(s1) == window size

from collections import Counter
def checkInclusion(self, s1: str, s2: str) -> bool:
    
    needs = Counter(s1)
    counter = len(s1)
    
    left = right = 0
    
    while right < len(s2):
        
        c = s2[right]
        if c in needs:
            needs[c] -= 1
            counter -= needs[c] >= 0
        right += 1
        
        while not counter:
            if right - left == len(s1):
                return True
            c = s2[left]
            if c in needs:
                needs[c] += 1
                counter += needs[c] > 0
            left += 1
    
    return False

438. Find All Anagrams in a String

from collections import Counter
def findAnagrams(self, s: str, p: str) -> List[int]:
    needs = Counter(p)
    counter = len(p)
    left = right = 0
    res = []
    
    while right < len(s):
        c = s[right]
        if c in needs:
            needs[c] -= 1
            counter -= needs[c] >= 0
        right += 1
        
        # is a valid window
        while not counter:
            c = s[left]
            if (right - left) == len(p):
                res.append(left)
            if c in needs:
                needs[c] += 1
                counter += needs[c] > 0
            left += 1
    return res

3. Longest Substring Without Repeating Characters

from collections import defaultdict
def lengthOfLongestSubstring(self, s: str) -> int:
    
    cur = defaultdict(int)
    left = right = 0
    res = 0
    
    while right < len(s):
        cur[s[right]] += 1
        while cur[s[right]] > 1:
            cur[s[left]] -= 1
            left += 1
        right += 1
        res = max(res, right - left)
            
    return res 

239. Sliding Window Maximum

from collections import deque
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    
    def window_push(n):
        # delete all element less than n
        while window and window[-1] < n:
            window.pop()
        window.append(n)
    
    def window_get_max():
        return window[0] if window else None
    
    def window_pop(n):
        return window.popleft() if window and n == window[0] else None
    
    window = deque([])
    res = []
    for i, n in enumerate(nums):
        window_push(n)
        
        if i >= k - 1:
            # generate res when i >= k - 1
            res.append(window_get_max())
            
            # remove left
            window_pop(nums[i - k + 1])
    
    return res