Buckets:
| tags: | |
| - notes | |
| - sliding-window | |
| ### [Best Time to Buy and Sell Stock](https://neetcode.io/problems/buy-and-sell-crypto) 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`. | |
| ```python | |
| 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. | |
| ```python | |
| 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](https://neetcode.io/problems/longest-substring-without-duplicate) 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). | |
| ```python | |
| 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 | |
| ```python | |
| 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](https://neetcode.io/problems/longest-repeating-substring-with-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. | |
| ```python | |
| 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`. | |
| ```python | |
| 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.