Sliding Window

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

引き続き取っつやすい分野ではあるけど、Two Pointers とかと比較するとちょっと難易度上がるなという印象。

29. Best Time to Buy And Sell Stock

Problem

You are given an integer array prices where prices[i] is the price of NeetCoin on the ith day.

You may choose a single day to buy one NeetCoin and choose a different day in the future to sell it.

Return the maximum profit you can achieve. You may choose to not make any transactions, in which case the profit would be 0.

Example 1:

Input: prices = [10,1,5,6,7,1]

Output: 6

Explanation: Buy prices[1] and sell prices[4], profit = 7 - 1 = 6.

Example 2:

Input: prices = [10,8,7,5,2]

Output: 0

Explanation: No profitable transactions can be made, thus the max profit is 0.

Constraints:

1 <= prices.length <= 100

0 <= prices[i] <= 100

Solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        min_price = math.inf

        for price in prices:
            if price > min_price:
                max_profit = max(max_profit, price - min_price)
            min_price = min(min_price, price)
        
        return max_profit

30. Longest Substring Without Repeating Characters

Problem

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

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "zxyzxyz"

Output: 3

Explanation: The string "xyz" is the longest without duplicate characters.

Example 2:

Input: s = "xxxx"

Output: 1

Constraints:

0 <= s.length <= 1000

s may consist of printable ASCII characters.

Solution

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l = 0
        hash_set = set()
        longest = 0

        for r in range(len(s)):
            while s[r] in hash_set:
                hash_set.remove(s[l])
                l+=1
                
            hash_set.add(s[r])
            longest = max(longest, r - l + 1)
        
        return longest

31. Longest Repeating Character Replacement

Problem

You are given a string s consisting of only uppercase english characters and an integer k. You can choose up to k characters of the string and replace them with any other uppercase English character.

After performing at most k replacements, return the length of the longest substring which contains only one distinct character.

Example 1:

Input: s = "XYYX", k = 2

Output: 4

Copy

Explanation: Either replace the 'X's with 'Y's, or replace the 'Y's with 'X's.

Example 2:

Input: s = "AAABABB", k = 1

Output: 5

Copy

Constraints:

• 1 <= s.length <= 1000
• 0 <= k <= s.length

Solution

from collections import defaultdict

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        longest = 0
        l = 0
        max_freq = 0
        char_count_map = defaultdict(int)

        for r in range(len(s)):
            char_count_map[s[r]] += 1
            if char_count_map[s[r]] > max_freq:
                max_freq = char_count_map[s[r]]
            
            if (r - l + 1) - max_freq <= k:
                # window size から最大頻度を引いた値が
                # K以下の場合、重複を含まないsubstringとして使える
                longest = max(longest, r-l+1)
            else:
                # window size から最大頻度を引いた値が
                # Kより大きい場合、windowを縮小しなきゃいけない
                char_count_map[s[l]] -= 1
                l += 1
                
                # ここで再度char_count_map全体を見て
                # max_freqの値も更新する必要がある気がするが、
                # ここで更新したってlongestの値がもっと長くなることはないのと、
                # もっと長くなるチャンスがある時はmax_freqもちゃんと更新されるので、不要
        
        return longest

32. Permutation In String

Problem

You are given a string s consisting of only uppercase english characters and an integer k. You can choose up to k characters of the string and replace them with any other uppercase English character.

After performing at most k replacements, return the length of the longest substring which contains only one distinct character.

Example 1:

Input: s = "XYYX", k = 2

Output: 4

Copy

Explanation: Either replace the 'X's with 'Y's, or replace the 'Y's with 'X's.

Example 2:

Input: s = "AAABABB", k = 1

Output: 5

Copy

Constraints:

• 1 <= s.length <= 1000
• 0 <= k <= s.length

Solution

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        
        s1_ascii_array = [0] * 26
        s2_ascii_array = [0] * 26

        for i in range(len(s1)):
            ascii_s1 = ord(s1[i]) - ord('a')
            ascii_s2 = ord(s2[i]) - ord('a')

            s1_ascii_array[ascii_s1] += 1
            s2_ascii_array[ascii_s2] += 1
        
        matches = 0
        for i in range(26):
            if s1_ascii_array[i] == s2_ascii_array[i]:
                matches += 1
        
        l = 0
        for r in range(len(s1), len(s2)):
            if matches == 26:
                # 文字列のカウント数が等しいのでTrueを返す
                return True
            
            # 新しい文字のカウントを足す
            ascii_r = ord(s2[r]) - ord('a')
            s2_ascii_array[ascii_r] += 1

            # 新しく足した文字のカウントがs1の文字のカウントと等しければmatchesをincrement
            if s2_ascii_array[ascii_r] == s1_ascii_array[ascii_r]:
                matches += 1
            # 元々等しかった場合はmatchesを減らす
            elif s2_ascii_array[ascii_r] - 1 == s1_ascii_array[ascii_r]:
                matches -= 1

            # window_sizeを縮小する際にlの文字カウントを減らす
            ascii_l = ord(s2[l]) - ord('a')
            s2_ascii_array[ascii_l] -= 1

            # 減らした文字のカウントがs1の文字のカウントと等しければmatchesをincrement
            if s2_ascii_array[ascii_l] == s1_ascii_array[ascii_l]:
                matches += 1
            # 元々等しかった場合はmatchesを減らす
            elif s2_ascii_array[ascii_l] + 1 == s1_ascii_array[ascii_l]:
                matches -= 1
            
            l += 1
        
        # 最後の文字に到達した後の比較はまだできてないので、ここで比較する
        return matches == 26

33. Minimum Window Substring

Problem

Given two strings s and t, return the shortest substring of s such that every character in t, including duplicates, is present in the substring. If such a substring does not exist, return an empty string "".

You may assume that the correct output is always unique.

Example 1:

Input: s = "OUZODYXAZV", t = "XYZ"

Output: "YXAZ"

Copy

Explanation: "YXAZ" is the shortest substring that includes "X", "Y", and "Z" from string t.

Example 2:

Input: s = "xyz", t = "xyz"

Output: "xyz"

Copy

Example 3:

Input: s = "x", t = "xy"

Output: ""

Copy

Constraints:

• 1 <= s.length <= 1000
• 1 <= t.length <= 1000
• s and t consist of uppercase and lowercase English letters.

Solution

from collections import Counter, defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(t) > len(s):
            return ''
        
        t_counter = Counter(t)
        s_counter = defaultdict(int)

        # ユニークな文字列の数が必要な数
        NEED = len(t_counter.keys())

        # tの文字のカウントを上回る文字がwindowの中にあれば+1
        HAVE = 0

        for i in range(len(t)):
            s_counter[s[i]] += 1

            if s_counter[s[i]] == t_counter[s[i]]:
                HAVE += 1
        
        # sの最初のtの長さまでの文字とtの文字カウントが等しいのでそれを返す
        if HAVE == NEED:
            return s[:len(t)]

        l = 0
        shortest = ''
        shortest_len = math.inf

        for r in range(len(t), len(s)):
            s_counter[s[r]] += 1
            if s_counter[s[r]] == t_counter[s[r]]:
                HAVE += 1
            
            while HAVE == NEED:
                if (r - l + 1) < shortest_len:
                    shortest = s[l:r+1]
                    shortest_len = r - l + 1
                
                s_counter[s[l]] -= 1
                if s_counter[s[l]] + 1 == t_counter[s[l]]:
                    HAVE -= 1
                l += 1
        
        return shortest

34. Sliding Window Maximum

Problem

You are given an array of integers nums and an integer k. There is a sliding window of size k that starts at the left edge of the array. The window slides one position to the right until it reaches the right edge of the array.

Return a list that contains the maximum element in the window at each step.

Example 1:

Input: nums = [1,2,1,0,4,2,6], k = 3

Output: [2,2,4,4,6]

Explanation: 
Window position            Max
---------------           -----
[1  2  1] 0  4  2  6        2
 1 [2  1  0] 4  2  6        2
 1  2 [1  0  4] 2  6        4
 1  2  1 [0  4  2] 6        4
 1  2  1  0 [4  2  6]       6

Copy

Constraints:

• 1 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• 1 <= k <= nums.length

Solution

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = deque() # index

        res = []
        l = 0
        for r in range(len(nums)):
            while queue and nums[queue[-1]] < nums[r]:
                queue.pop()
            
            queue.append(r)

            # window sizeがkと等しくなったらresに最大値を追加する
            # 最大値はqueueの左端にある値
            # window sizeがk以上になったら、
            # queueの左端のindexがlと等しければpopleftしてlをincrement
            if r - l + 1 >= k:
                res.append(nums[queue[0]])

                if l == queue[0]:
                    queue.popleft()
                l += 1
        
        return res