Array — Sliding Window

LeetCode(3) – Longest Substring Without Repeating Characters https://leetcode.com/problems/longest-substring-without-repeating-characters/

Wrong Code:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """  
        Sliding Window: s[i, j] is the substring containing non-repeat characters.
        Then, try to extend j, otherwise, extend i.
        """
        char_pos = {}
        i, j = 0, 0
        res = 0
        while i < len(s): # standard for loop of sliding window
            if j + 1 < len(s) and s[j + 1] in char_pos:
                i = char_pos[s[j + 1]] + 1 # problem is here. cannot jump on i.
                del char_pos[s[j + 1]]
            else:
                j += 1
                char_pos[s[j]] = j 
            res = max(res, j - i + 1)
        return res

Code:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """  
        Sliding Window: s[i, j] is the substring containing non-repeat characters.
        Then, try to extend j, otherwise, extend i.
        """
        freq = [0 for i in range(256)]
        i, j = 0, -1
        res = 0
        while i < len(s): # standard for loop of sliding window
            if j + 1 < len(s) and freq[ord(s[j+1])] == 0:
                j += 1
                freq[ord(s[j])] += 1 
            else:
                freq[ord(s[i])] -= 1
                i += 1
            res = max(res, j - i + 1)
        return res

LeetCode(438) Find All Anagrams in a String https://leetcode.com/problems/find-all-anagrams-in-a-string/

Code:

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        """
        anagram: the substring of s contains all characters in p and appear 
                 the same number of times
        """
        res = []
        chars = {}
        to_match = len(p)   
        for char in p:
            chars[char] = chars[char] + 1 if char in chars else 1
            
        i, j = 0, -1
        while i < len(s) - len(p) + 1:
            # if len(substring) is less than len(p), extend the substring
            if j - i + 1< len(p):
                j += 1
                if s[j] in chars:
                    chars[s[j]] -= 1
                    # substract to_match only for non-redandunt character
                    to_match = to_match - 1 if chars[s[j]] >= 0 else to_match
            else:
                if to_match == 0:
                    res.append(i)
                # pop s[i]
                if s[i] in chars:
                    chars[s[i]] += 1
                    # increase to_match only for non_redandunt character
                    to_match = to_match + 1 if chars[s[i]] > 0 else to_match
                i += 1
                    
        return res

This is what I saw in LeetCode, elegant codes. It does not declare much space but use hash to calculate and compare. Anagram: the hash of 2 strings should be the same.

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
    	LS, LP, S, P, A = len(s), len(p), 0, 0, []
    	if LP > LS: return []
    	for i in range(LP): S, P = S + hash(s[i]), P + hash(p[i])
    	if S == P: A.append(0)
    	for i in range(LP, LS):
    		S += hash(s[i]) - hash(s[i-LP])
    		if S == P: A.append(i-LP+1)
    	return A

another solution: use list to calculate how many times each character appears in substring of s and p. then compare two 26-elements list in each loop iteration. it is also constant time.

LeetCode 76. Minimum Window Substring https://leetcode.com/problems/minimum-window-substring/

Code:

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        res = ""
        i, j = 0, -1
        to_match = len(t)
        chars = {}
        for char in t:
            chars[char] = chars[char] + 1 if char in chars else 1
        
        while i < len(s):
            if to_match > 0 and j < len(s) - 1:
                j += 1
                if s[j] in chars:
                    chars[s[j]] -= 1
                    to_match = to_match - 1 if chars[s[j]] >= 0 else to_match
            elif to_match > 0 and j >= len(s) - 1:
                break
            else:
                if res == "" or (j - i) < len(res):
                    res = s[i:j+1]
                if s[i] in chars:
                    chars[s[i]] += 1
                    to_match = to_match + 1 if chars[s[i]] > 0 else to_match
                i += 1
        return res   

LeetCode 209. Minimum Size Subarray Sum https://leetcode.com/problems/minimum-size-subarray-sum/

Code:

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

Leave a Reply

Your email address will not be published. Required fields are marked *