Sliding Window

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:** ```java Input: prices = [10,1,5,6,7,1] Output: 6 ``` Explanation: Buy `prices[1]` and sell `prices[4]`, `profit = 7 - 1 = 6`. **Example 2:** ```java 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` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to iterate through the array with index <code>i</code>, considering it as the day to buy, and trying all possible options for selling it on the days to the right of index <code>i</code>. This would be an <code>O(n^2)</code> solution. Can you think of a better way? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> You should buy at a price and always sell at a higher price. Can you iterate through the array with index <code>i</code>, considering it as either the buying price or the selling price? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can iterate through the array with index <code>i</code>, considering it as the selling value. But what value will it be optimal to consider as buying point on the left of index <code>i</code>? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We are trying to maximize <code>profit = sell - buy</code>. If the current <code>i</code> is the sell value, we want to choose the minimum buy value to the left of <code>i</code> to maximize the profit. The result will be the maximum profit among all. However, if all profits are negative, we can return <code>0</code> since we are allowed to skip doing transaction. </p> </details>

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:** ```java Input: s = "zxyzxyz" Output: 3 ``` Explanation: The string "xyz" is the longest without duplicate characters. **Example 2:** ```java Input: s = "xxxx" Output: 1 ``` **Constraints:** * `0 <= s.length <= 1000` * `s` may consist of printable ASCII characters. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(m)</code> space, where <code>n</code> is the length of the string and <code>m</code> is the number of unique characters in the string. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to try the substring starting at index <code>i</code> and try to find the maximum length we can form without duplicates by starting at that index. we can use a hash set to detect duplicates in <code>O(1)</code> time. Can you think of a better way? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use the sliding window algorithm. Since we only care about substrings without duplicate characters, the sliding window can help us maintain valid substring with its dynamic nature. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can iterate through the given string with index <code>r</code> as the right boundary and <code>l</code> as the left boundary of the window. We use a hash set to check if the character is present in the window or not. When we encounter a character at index <code>r</code> that is already present in the window, we shrink the window by incrementing the <code>l</code> pointer until the window no longer contains any duplicates. Also, we remove characters from the hash set that are excluded from the window as the <code>l</code> pointer moves. At each iteration, we update the result with the length of the current window, <code>r - l + 1</code>, if this length is greater than the current result. </p> </details>

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:** ```java 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:** ```java Input: s = "AAABABB", k = 1 Output: 5 ``` **Constraints:** * `1 <= s.length <= 1000` * `0 <= k <= s.length` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(m)</code> space, where <code>n</code> is the length of the given string and <code>m</code> is the number of unique characters in the string. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Which characters would you replace in a string to make all its characters identical? Can you think with respect to the frequency of the characters? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> It is always optimal to replace characters with the most frequent character in the string. Why? Because using the most frequent character minimizes the number of replacements required to make all characters in the string identical. How can you find the number of replacements now? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> The number of replacements is equal to the difference between the length of the string and the frequency of the most frequent character in the string. A brute force solution would be to consider all substrings, use a hash map for frequency counting, and return the maximum length of the substring that has at most <code>k</code> replacements. This would be an <code>O(n^2)</code> solution. Can you think of a better way? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use the sliding window approach. The window size will be dynamic, and we will shrink the window when the number of replacements exceeds <code>k</code>. The result will be the maximum window size observed at each iteration. </p> </details>

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:** ```java Input: s1 = "abc", s2 = "lecabee" Output: true ``` Explanation: The substring `"cab"` is a permutation of `"abc"` and is present in `"lecabee"`. **Example 2:** ```java Input: s1 = "abc", s2 = "lecaabee" Output: false ``` **Constraints:** * `1 <= s1.length, s2.length <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the maximum of the lengths of the two strings. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would be to check every substring of <code>s2</code> with <code>s1</code> by sorting <code>s1</code> as well as the substring of <code>s2</code>. This would be an <code>O(n^2)</code> solution. Can you think of a better way? Maybe we can use the freqency of the characters of both the strings as we did in checking anagrams. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We return false if the length of <code>s1</code> is greater than the length of <code>s2</code>. To count the frequency of each character in a string, we can simply use an array of size <code>O(26)</code>, since the character set consists of <code>a</code> through <code>z</code> (<code>26</code> continuous characters). Which algorithm can we use now? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We use a sliding window approach on <code>s2</code> with a fixed window size equal to the length of <code>s1</code>. To track the current window, we maintain a running frequency count of characters in <code>s2</code>. This frequency count represents the characters in the current window. At each step, if the frequency count matches that of <code>s1</code>, we return <code>true</code>. </p> </details>

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:** ```java Input: s = "OUZODYXAZV", t = "XYZ" Output: "YXAZ" ``` Explanation: `"YXAZ"` is the shortest substring that includes `"X"`, `"Y"`, and `"Z"` from string `t`. **Example 2:** ```java Input: s = "xyz", t = "xyz" Output: "xyz" ``` **Example 3:** ```java Input: s = "x", t = "xy" Output: "" ``` **Constraints:** * `1 <= s.length <= 1000` * `1 <= t.length <= 1000` * `s` and `t` consist of uppercase and lowercase English letters. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(m)</code> space, where <code>n</code> is the length of the string <code>s</code> and <code>m</code> is the number of unique characters in <code>s</code> and <code>t</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would involve checking every substring of <code>s</code> against <code>t</code> and returning the minimum length valid substring. This would be an <code>O(n^2)</code> solution. Can you think of a better way? Maybe you should think in terms of frequency of characters. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We need to find substrings in <code>s</code> that should have atleast the characters of <code>t</code>. We can use hash maps to maintain the frequencies of characters. It will be <code>O(1)</code> for lookups. Can you think of an algorithm now? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use a dynamically sized sliding window approach on <code>s</code>. We iterate through <code>s</code> while maintaining a window. If the current window contains at least the frequency of characters from <code>t</code>, we update the result and shrink the window until it is valid. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We should ensure that we maintain the result substring and only update it if we find a shorter valid substring. Additionally, we need to keep track of the result substring's length so that we can return an empty string if no valid substring is found. </p> </details>

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:** ```java 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 ``` **Constraints:** * `1 <= nums.length <= 1000` * `-10,000 <= nums[i] <= 10,000` * `1 <= k <= nums.length` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(nlogn)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force solution would involve iterating through each window of size <code>k</code> and finding the maximum element within the window by iterating through it. This would be an <code>O(n * k)</code> solution. Can you think of a better way? Maybe think of a data structure that tells the current maximum element of the window in <code>O(1)</code> time. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> A heap is the best data structure to use when dealing with maximum or minimum values and it takes <code>O(1)</code> time to get the max or min value. Here, we use a max-heap. But what should we do if the current maximum element is no longer part of the window? Can you think of a different way of adding values to the max-heap? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We process each window by adding elements to the heap along with their indices to track whether the maximum value is still within the current window. As we move from one window to the next, an element may go out of the window but still remain in the max-heap. Is there a way to handle this situation efficiently? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can ignore those elements that are no longer part of the current window, except when the maximum value is outside the window. In that case, we remove elements from the max-heap until the maximum value belongs to the current window. Why? Because those elements will be eventually removed when the maximum element goes out of the window. </p> </details>