DenCT/test-storage / DSA Notes /Sliding Window.md
DenCT's picture
|
download
raw
9.15 kB
metadata
tags:
  - notes
  - sliding-window

Best Time to Buy and Sell Stock EASY

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.

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

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

[!info] Time and Space Complexity You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Solution

To find the maximum profit from a single buy and sell transaction in the input array prices, we can use a simple one-pass approach. We initialize two variables, min_price to keep track of the minimum price seen so far, and max_profit to store the maximum profit. We iterate through the prices array, and for each price, we update the min_price if we find a smaller price. We also calculate the potential profit if we sell at the current price and update max_profit if the current profit is greater than the previous maximum profit.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy = 0
        profit = 0
        for sell in range(1, len(prices)):
            if prices[sell] < prices[buy]:
                buy = sell
            profit = max(profit, prices[sell] - prices[buy])
        return profit if profit > 0 else 0

Longest Substring Without Repeating Characters MEDIUM

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

[!info] Time and Space Complexity You should aim for a solution with O(n) time and O(m) space, where n is the length of the string and m is the number of unique characters in the string.

Solution

To find the length of the longest substring without repeating characters in the input string 's', we can use the sliding window approach. We use two pointers, 'left' and 'right', to represent the current window. As we move the 'right' pointer to the right, we expand the window and add characters to a set to keep track of unique characters in the window. If we encounter a repeating character, we move the 'left' pointer to the right to shrink the window until the repeating character is no longer in the window. At each step, we update the maximum length of the window (i.e., the length of the longest substring without repeating characters).

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        unique_chars = {}
        max_len = 0
        start = 0
        size = len(s)
        for end in range(size):
            if s[end] in unique_chars:
                start = max(unique_chars[s[end]] + 1, start)
            unique_chars[s[end]] = end
            max_len = max(max_len, end - start + 1)
        return max_len

Fruits into Baskets

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces. You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

  • You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
  • Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
  • Once you reach a tree with fruit that cannot fit in your baskets, you must stop. Given the integer array fruits, return the maximum number of fruits you can pick. Example 1:
Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.

Example 2:

Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].

Example 3:

Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: We can pick from trees [2,3,2,2].
If we had started at the first tree, we would only pick from trees [1,2].

Solution

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        left = 0
        max_count = 1 if fruits else 0
        counts = {
            fruits[0]: 1
        }
        for right in range(1, len(fruits)):
            counts[fruits[right]] = counts.get(fruits[right], 0) + 1
            while len(counts) > 2:
                counts[fruits[left]] -= 1
                if counts[fruits[left]] == 0:
                    del counts[fruits[left]]
                left += 1
            max_count = max(max_count, right - left + 1)
        return max_count

Longest Repeating Character Replacement MEDIUM

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

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

Solution

To find the maximum length of a substring with at most k distinct characters in the input string s, we can use the sliding window approach. We use two pointers, left and right, to represent the current window. As we move the right pointer to the right, we expand the window and add characters to a dictionary to keep track of their frequencies. If the number of distinct characters in the window exceeds k, we move the left pointer to the right to shrink the window until the number of distinct characters is k again. At each step, we update the maximum length of the window.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        chars = {}
        l = 0
        max_len = 0
        max_count = 0
        for r in range(len(s)):
            chars[s[r]] = chars.get(s[r], 0) + 1
            max_count = max(max_count, chars[s[r]])

            while (r - l + 1) - max_count > k:
                chars[s[l]] -= 1
                l += 1

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

[!info] Time and Space Complexity You should aim for a solution with O(n) time and O(m) space, where n is the length of the given string and m is the number of unique characters in the string.

Permutation in String MEDIUM

You are given two strings s1 and s2. Return true if s2 contains a permutation of s1, or false otherwise. That means if a permutation of s1 exists as a substring of s2, then return true. Both strings only contain lowercase letters.

**Example 1:**

Input: s1 = "abc", s2 = "lecabee"
Output: true

Explanation: The substring "cab" is a permutation of "abc" and is present in "lecabee".

Example 2:

Input: s1 = "abc", s2 = "lecaabee"
Output: false

[!info] Time and Space Complexity You should aim for a solution with O(n) time and O(1) space, where n is the maximum of the lengths of the two strings.

Solution

To check whether a string s2 contains a permutation of another string s1, we can use a sliding window approach. First, we create a frequency dictionary for characters in s1. Then, we initialize two pointers, left and right, to represent the current window in s2. As we move the right pointer to the right, we add the character to a temporary frequency dictionary and check if it becomes equal to the frequency dictionary of s1. If it does, it means we found a permutation of s1 in s2, and we return True. If the window size exceeds the length of s1, we remove the character at the left pointer from the temporary dictionary and move the left pointer to the right to shrink the window. We continue this process until we find a permutation or reach the end of s2.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        char_freq_s1 = {}
        for char in s1:
            char_freq_s1[char] = char_freq_s1.get(char, 0) + 1
        left, right = 0, 0
        char_freq_temp = {}
        while right < len(s2):
            char_freq_temp[s2[right]] = char_freq_temp.get(s2[right], 0) + 1
            if right - left + 1 == len(s1):
                if char_freq_temp == char_freq_s1:
                    return True
                char_freq_temp[s2[left]] -= 1
                if char_freq_temp[s2[left]] == 0:
                    del char_freq_temp[s2[left]]
                left += 1
            right += 1
        return False

Xet Storage Details

Size:
9.15 kB
·
Xet hash:
f235ff67828c1cefe4d7ac2a5a578d952736421daabb9eff4c4e76bddee3a9aa

Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.