#SildingWindow

[Notes] Sliding Window

Posted by 西维蜀黍的OJ Blog on 2023-09-13, Last Modified on 2025-03-25

滑动窗口算法

说起滑动窗口算法，很多读者都会头疼。这个算法技巧的思路非常简单，就是维护一个窗口，不断滑动，然后更新答案么。LeetCode 上有起码 10 道运用滑动窗口算法的题目，难度都是中等和困难。该算法的大致逻辑如下：

int left = 0, right = 0;

while (left < right && right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

这个算法技巧的时间复杂度是 O(N)，比字符串暴力算法要高效得多。

另外，虽然滑动窗口代码框架中有一个嵌套的 while 循环，但算法的时间复杂度依然是 O(N)，其中 N 是输入字符串/数组的长度。

为什么呢？简单说，指针 left, right 不会回退（它们的值只增不减），所以字符串/数组中的每个元素都只会进入窗口一次，然后被移出窗口一次，不会说有某些元素多次进入和离开窗口，所以算法的时间复杂度就和字符串/数组的长度成正比。

解析

3. Longest Substring Without Repeating Characters

  • 用一个 window (map) 来记录已经遇到的字符，并扫描每一个字符
    • 如果遇到了没碰到过的字符（不在 window）中，把该字符加到 window中（expand the window, i.e., increment r）
    • 如果遇到了已经碰到过的字符（在 window）中，比如abcc，shrink the window (increase l) 直到 s[l] == s[r]，此后再次移动 l
	# sliding window - 写法1 (myself)
	# - time: O(n) # the length of the string 
	# - space: O(m) # the total number of unique characters in the string
   def lengthOfLongestSubstring(self, s):
        res = 0
        window = set()
        l = 0
        for r in range(len(s)):
            if s[r] not in window:  # 如果遇到一个新字符，expand the window
                window.add(s[r])
                res = max(res, len(window))
            else:
                while s[l] != s[r]:  # 如果遇到一个已经遇到过的字符，shrink the window
                    window.remove(s[l])
                    l += 1
                l += 1

        return res
      
	# sliding window - 写法1 (myself)
	# - time: O(n) # the length of the string 
	# - space: O(m) # the total number of unique characters in the string
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        l = 0
        res = 0

        for r in range(len(s)):
            while s[r] in charSet: # shrink the window first
                charSet.remove(s[l])
                l += 1
            # after make sure the window is valid, expand the window    
            charSet.add(s[r])
            res = max(res, r - l + 1)
        return res 

	# sliding window - 写法1 (neetcode optimal)
	# - time: O(n) # the length of the string 
	# - space: O(m) # the total number of unique characters in the string      
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        mp = {}  # 用一个map来记住之前遇到过的元素对应坐标，因而 shrink 的时候，只需要 O(1)，而不需要 O(n)
        l = 0
        res = 0

        for r in range(len(s)):
            if s[r] in mp:  # shrink the window
                # 需要用 max 而不能 mp[s[r]] + 1，因为存在 mp[s[r]] + 1 比 l 小的情况，
                # 比如 "abba", 在 r = 3时，mp[s[r]] + 1 为 1，而 l 为 2，此时 l 应该取 2
                l = max(mp[s[r]] + 1, l)
            mp[s[r]] = r
            res = max(res, r - l + 1)
            print(r, res)
        return res

ref

76. Minimum Window Substring

	# solution 1 - sliding window
	# - time: O(s), since one element in s will be push/pop to the window once respectively
	# - space: O(1)
	def minWindow(self, s: str, t: str) -> str:
		tCount = {}
		for char in t:  # time: O(t)
			tCount[char] = tCount.get(char, 0) + 1
		tKeyCount = len(tCount)  # the number of char to be satisfied

		curMinLen = 0
		res = ""

		curWindow = {}  # the window
		curSatisfiedKeyCount = 0
		l = 0
		for r in range(len(s)):  # time: O(s)
			char = s[r]
			curWindow[char] = curWindow.get(char, 0) + 1

			if char in tCount and curWindow[char] == tCount[char]:  # the number of char has satisfied
				curSatisfiedKeyCount += 1

			while curSatisfiedKeyCount == tKeyCount:  # means that t is the substring of the current window
				# update the result
				if curMinLen == 0 or (curMinLen != 0 and (r - l + 1) < curMinLen):  # found an eligible substring
					res = s[l:r + 1]
					curMinLen = r - l + 1

				# shrink the window
				curWindow[s[l]] -= 1
				if s[l] in tCount and curWindow[s[l]] < tCount[s[l]]:
					curSatisfiedKeyCount -= 1
				l += 1

		return res

ref

121. Best Time to Buy and Sell Stock

# brute force
#  - time: O(n^2)
#  - space: O(1)
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        for i in range(len(prices)):
            buy = prices[i]
            for j in range(i + 1, len(prices)):
                sell  = prices[j]
                res = max(res, sell - buy)
        return res
      
      
# two point - 写法1
#  - time: O(n)
#  - space: O(1)
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        lowest_price = prices[0] # lowest price seen so far
        max_profit = 0
        for r in range(len(prices)):
            if prices[r] < lowest_price:  # shrink the window if needed
                lowest_price = prices[r]
            curr_profit = prices[r] - lowest_price
            max_profit = max(max_profit, curr_profit)
        return max_profit
		
# sliding window - 写法2
#  - time: O(n)
#  - space: O(1)
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        max_profit = 0
        l = 0
        for r in range(1, len(prices)):
            if prices[r] > prices[l]: # profitable?
                cur_profit = prices[r] - prices[l]
                max_profit = max(max_profit, cur_profit)
            else:
                l = r

        return max_profit

ref

219. Contains Duplicate II

  • abs(i - j) <= k means size of the window is <= k
# brute force
#  - time: o(nk)
#  - space: O(n)


# sliding window
#  - time: o(n)
#  - space: O(k)
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        window = set()
        l = 0
        for r in range(len(nums)):
            if r - l > k: # shrink the window first if need
                window.remove(nums[l])
                l += 1

            if nums[r] in window:
                return True
            window.add(nums[r])

        return False

122. Best Time to Buy and Sell Stock II

# two points
#  - time: o(n)
#  - space: O(1)
   def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        lowest_price = prices[0]
        total_profit = 0
        for r in range(len(prices)):
            if prices[r] > lowest_price:  # if profitable, sell. Then update the can-buy price
                total_profit += prices[r] - lowest_price
            lowest_price = prices[r]
        return total_profit

ref

239. Sliding Window Maximum

TODO

* 309. Best Time to Buy and Sell Stock with Cooldown

decision tree + cache:

  • without caching: O(2^n)
  • With caching: O(n)

# recursion
# time: O(2^n)
# space: O(1)
def maxProfit(self, prices: List[int]) -> int:
        def dfs(i, buying):
            if i >= len(prices):
                return 0
            
            cooldown = dfs(i + 1, buying)
            if buying:
                buy = dfs(i + 1, not buying) - prices[i]
                return max(buy, cooldown)
            else:
                sell = dfs(i + 2, not buying) + prices[i]
                return max(sell, cooldown)
        
        return dfs(0, True)
      
# DP (top-down)      
# time: O(n)
# space: O(n)
class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # State: buy or sell
        # If buy -> i + 1
        # if Sell -> i + 2 (because of cooldown day)
        dp = {}  # key=(i, buying) val=max_profit

        def dfs(i, buying):
            if i >= len(prices):
                return 0
            if (i, buying) in dp:
                return dp[(i, buying)]

            if buying:
                buy = dfs(i + 1, not buying) - prices[i]
                cooldown = dfs(i + 1, True)
                dp[(i, buying)] = max(buy, cooldown)
            else:
                sell = dfs(i + 2, not buying) + prices[i]
                cooldown = dfs(i + 1, False)
                dp[(i, buying)] = max(sell, cooldown)
            return dp[(i, buying)]

        return dfs(0, True)

ref

424. Longest Repeating Character Replacement

  • 替换策略：把用出现次数最多的字符替换其他字符
    • 用 count map （window）把每个字符出现的次数记录下来，每次 for loop 这个 count map 来找到出现次数最多的字符
    • 计算出出现次数最多的字符出现的次数，记为 max_len，用total_len - max_len <=k 以判断其是否为合法字符串
# brute force
#  - time: O(n^2)
#  - space: O(n)

# sliding window - myself - 利用只会出现大写字符 O(26n) -> O(n)
# time: O(n) # length of the given string
# space: O(m) # the number of unique characters in the string
  def characterReplacement(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        max_repeating_len = 0
        l = 0
        m = {}  # space: o(n)
        for r in range(len(s)):  # time: O(n)
            m[s[r]] = m.get(s[r], 0) + 1

            while l < r:  # scan the current window
                total_len = 0
                max_len = 0
                for char, v in m.items():  # time: O(26)
                    total_len += v
                    if v > max_len:
                        max_len = v

                if total_len - max_len <= k:  # shrink-window condition
                    max_repeating_len = max(max_repeating_len, total_len)
                    break
                else:  # shrink the window
                    m[s[l]] = m[s[l]] - 1
                    l += 1
        return max_repeating_len

# sliding window - neetcode - 利用只会出现大写字符 O(26n) -> O(n)
# time: O(n) # length of the given string -> O(26n)
# space: O(m) # the number of unique characters in the string
    def characterReplacement(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        max_repeating_len = 0
        l = 0
        m = {}  # space: o(n)
        for r in range(len(s)):  # time: O(n)
            m[s[r]] = m.get(s[r], 0) + 1

            while (r - l + 1) - max(m.values()) > k:
                m[s[l]] -= 1
                l += 1

            max_repeating_len = max(max_repeating_len, r - l + 1)
        return max_repeating_len

# ？？       
# sliding window - optinal solution
# length - maxf <= k
#  - 我们需要执行 O(26)， 来得到 length - maxf
#  - 如果 maxf 变大，length - maxf 的值只会变小。反之，  length - maxf 的值会变大。
#  - 因而，只需要关心 length - maxf 的值只会变小的情况，因为我们希望找到更好的 
    def characterReplacement(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        max_repeating_len = 0
        l = 0
        m = {}  # space: o(n)
        max_f = 0
        for r in range(len(s)):  # time: O(n)
            m[s[r]] = m.get(s[r], 0) + 1
            max_f = max(max_f, m[s[r]])

            while (r - l + 1) - max_f > k:
                m[s[l]] -= 1
                l += 1

            max_repeating_len = max(max_repeating_len, r - l + 1)
        return max_repeating_len

ref

todo - 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

Ref

FEATURED TAGS
graph hashmap leetcode lintcode sortarray topic tree 剑指刷题

TOC