Sliding Window

Template

Time O(n)

int j = 0
for i in range(n):
    while j<n && array 不滿足條件
         j+=1
         拓寬條件
     if array 滿足條件
         看是不是最優的
     num[i]移出array

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

T: O(2n)

def lengthOfLongestSubstring(self, s: str) -> int:
    record = set()
    res = 0
    i, j = 0, 0
    
    while j < len(s):
        while j < len(s) and s[j] not in record:
            record.add(s[j])
            j+=1
        res = max(res, j-i)
        record.remove(s[i])
        i+=1
    
    return res

T: O(n), S: O(n)

def lengthOfLongestSubstring(self, s: str) -> int:
    record = collections.defaultdict(int)
    res = 0
    i = 0
    
    for j, c in enumerate(s):
        if c in record:
            i = max(i, record[c] + 1)
        res = max(res, j - i + 1)
        record[c] = j
    return res

340 Longest Substring with At Most K Distinct Characters

Given a string s, find the length of the longest substring T that contains at most k distinct characters.

• 利用map的size判斷k的數量

• 若超過找出left most character 的index

def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
    dic = defaultdict(int)
    ans = 0
    i, j = 0, 0
    
    while j < len(s):
        dic[s[j]] = j
       
        if len(dic) > k:
            i = len(s)
            for idx in dic.values():
                i = min(i, idx)
            del dic[s[i]]
            i += 1
        ans = max(ans, j-i+1) 
        j +=1
        
    return ans

76. 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).

Example:

Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"

def minWindow(self, s: str, t: str) -> str:
    dic = collections.Counter(t)
    record = collections.defaultdict(int)
    
    i, j = 0, 0
    ans = [-1, len(s)]
    
    for i in range(len(s)):
        ch = s[i]
        if ch not in dic: continue
        while j < len(s) and dic != record:
            ch_j = s[j]
            if ch_j in dic: record[ch_j] += 1
            j+=1 
        # 可能j走完但沒符合條件
        if dic == record and j-i < ans[1]-ans[0]:
            ans = [i,j]
        record[ch] -= 1
            
    return '' if ans[0] == -1 else s[ans[0]: ans[1]]

209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3] Output: 2

• Init i=0 and left=0, iterate over nums

def minSubArrayLen(self, s: int, nums: List[int]) -> int:
    i, j = 0, 0
    n = len(nums)
    ans = n+1
    total = 0
    
    while i<n:
        while j<n and total < s:
            total += nums[j]
            j+=1
        if total >= s:
            ans = min(ans, j-i)
        total -= nums[i]
        i+=1
        
    return ans if ans !=n+1 else 0

862. Shortest Subarray with Sum at Least K

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

1. 這題跟209的差異是num可能為負數

2. 用一個dequeue紀錄 sum and index, dequeue in increasing order by sum

3. Update if we can find total - sum >= k, and kind updating to shorten the distant

4. Explain

def shortestSubarray(self, A: List[int], K: int) -> int:       
    q = [[-1, 0]] # [index, total]
    total = 0        
    ans = float('inf')

    for i, n in enumerate(A):
        total += n            
        while q and total - q[0][1] >= K:
            ans = min(ans, i - q[0][0])
            q.pop(0)
        
        while q and total <= q[-1][1]:
            q.pop()
        q.append([i, total])
        
    return ans if ans != float('inf') else -1

395. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

• For loop n char, 代表每次check 只帶有 n char 的longest substring 的ans

• 2 counter: num of unique char and num of char more than k

• 只有在 count unique char == num of unique char && count of unique char == num of char more than k 才update

O(26 * n)

def longestSubstring(self, s: str, k: int) -> int:
    res = 0
    # possible unique char in answers
    for i in range(1, 27):
        res = max(res, self.helper(s, k, i))
        
    return res

def helper(self, s, k, numOfUniqueTarget):
    i, j = 0, 0
    numOfUnique = 0
    numOfNoLessThanK = 0
    record = collections.defaultdict(int)
    res = 0
    
    while j < len(s):
        if numOfUnique <= numOfUniqueTarget:
            if record[s[j]] == 0:
                numOfUnique +=1
            record[s[j]] += 1
            if record[s[j]] == k:
                numOfNoLessThanK += 1
            j += 1
        else:
            if record[s[i]] == k:
                numOfNoLessThanK -= 1
            record[s[i]] -= 1
            if record[s[i]] == 0:
                numOfUnique -= 1
            i += 1
            
        
         # if we found a string where the number of unique chars equals our target
         # and all those chars are repeated at least K times then update max
        if numOfUnique == numOfUniqueTarget and numOfUnique == numOfNoLessThanK:
            res = max(res, j-i)
            
    return res