# Sliding window
# 121. Best Time to Buy and Sell Stock
## Question
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
## Solution ("C")
```c=
int maxProfit(int* prices, int pricesSize){
// no sort
int start = 0;
int end = 1;
int profit = 0;
int maxima = 0;
while(start<=end&&end<pricesSize){
profit = -1*prices[start] + prices[end];
if(profit>maxima)
maxima = profit;
if(prices[end]<=prices[start]){
//start++;
start = end;
end++;
}
else{
end++;
}
}
return maxima;
}
```
## Notes:
* sliding window，如果收益是負的，start = end, end=end+1，繼續做iterative
* 需要紀錄maxima profit
* 這題蠻有意思的，也可以用dp解
---
# 3. Longest Substring Without Repeating Characters
## Question(Medium)
Given a string s, find the length of the longest
substring
without repeating characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
## Solution ("C")
```c=
int lengthOfLongestSubstring(char * s){
int record[200]={};
int length = strlen(s)-1;
int end = 0;
int start = 0;
int maxima = -1;
int count = 0;
if(strlen(s)==0)
return 0;
while(end<=length){
if(record[s[end]]!=0){
record[s[start]]=0;
start++;
count--;
}
else{
printf("%c %d", s[end], count);
record[s[end]]++;
end++;
count++;
}
if(count>maxima)
maxima = count;
}
return maxima;
}
```
## Notes:
* 有一個變數count，用來統計substring的size
* 若遇到重複的，start ptr++，count-1，這樣就不用每次都計算substring的大小
---
# 424. Longest Repeating Character Replacement
## Question (Medium)
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Example 1:
Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achive this answer too.
## Solution (C++)
```c=
class Solution {
public:
int characterReplacement(string s, int k) {
int start = 0, end = 0;
map<char, int> record;
int max_freq = -1;
int temp = 0;
int maxima = -1;
while(start<=end && end<s.length()){
record[s[end]]++;
max_freq = max(max_freq, record[s[end]]);
if(start==0 && end ==0){
end++;
continue;
}
temp = (1+(end-start) - max_freq);
if(temp<=k){
maxima = max(maxima, (1+(end-start)));
end++;
}
else{
record[s[start]]--;
record[s[end]]--;
start++;
}
}
return maxima;
}
};
```
## Notes:
* 這題用c++，使用map stl來記錄character出現的頻率
* sliding window來判斷(windows_size - max_freq <=k 代表可以replacement)
* 若windows_size-map_freq > k，則start_index++
---
# 1493. Longest Subarray of 1's After Deleting One Element
## Question (Medium)
Given a binary array nums, you should delete one element from it.
Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.
Example 1:
Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.
Example 2:
Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].
Example 3:
Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.
## Solution (C++)
```c=
class Solution {
public:
int longestSubarray(vector<int>& nums) {
if(nums.size()==1)
return 0;
int* left_record = new int[nums.size()]{};
int* right_record = new int[nums.size()]{};
int count = 0;
for(int i=0; i<nums.size(); i++){
if(nums[i]==1)
count++;
else
count = 0;
left_record[i] = count;
}
count = 0;
for(int i=nums.size()-1; i>=0; i--){
if(nums[i]==1)
count++;
else
count=0;
right_record[i] = count;
}
int max_length = 0;
int temp = 0;
for(int i=0; i<nums.size(); i++){
if(i==0){
temp = right_record[i+1];
}
else if(i==nums.size()-1){
temp = left_record[i-1];
}
else{
temp = left_record[i-1] + right_record[i+1];
}
if(temp>max_length)
max_length = temp;
}
return max_length;
}
};
```
## Notes:
* 我的寫法應該不是最優，但懶得優化
* 創建一個left_record 和 right_record的array，紀錄該index左右邊的longest subarray的長度。
---
# 1456. Maximum Number of Vowels in a Substring of Given Length
## Question (Medium)
Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.
Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.
Example 1:
Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.
Example 2:
Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.
Example 3:
Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.
## Solution (C++)
```c=
class Solution {
public:
bool is_vowel(char c){
if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
return true;
else
return false;
}
int maxVowels(string s, int k) {
int start = 0;
int end = k-1;
int vowel_count = 0;
int maxima = 0;
for(int i=0; i<s.length(); i++){
if(i<k){
if(is_vowel(s[i]))
vowel_count++;
maxima = vowel_count;
continue;
}
cout<<s[i]<<endl;
if(is_vowel(s[i-k]))
vowel_count--;
if(is_vowel(s[i]))
vowel_count++;
if(vowel_count>maxima)
maxima = vowel_count;
}
return (s.length()==k)?vowel_count:maxima;
}
};
```
## Notes:
* 用sliding window，往右滑。
* 如果遇到母音，則count+=1，也需要考慮第i-k個字母，如果本來是母音，則count-=1。
---
# 1004. Max Consecutive Ones III
## Question (Medium)
Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Example 2:
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
## Solution (C++)
```c=
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int count = 0, maxima = 0;
int start = 0, end = 0;
for(end=0; end<nums.size();){
if(nums[end]==1){
count++;
}
else if(nums[end]==0 && k>0){
count++;
k--;
}
else{
if(nums[start]==0){
k++;
}
start++;
count--;
continue;
}
if(count>maxima)
maxima = count;
end++;
}
return maxima;
}
};
```
## Notes
---
# 2063. Vowels of All Substrings
## Question (Medium)
Given a string word, return the sum of the number of vowels ('a', 'e', 'i', 'o', and 'u') in every substring of word.
A substring is a contiguous (non-empty) sequence of characters within a string.
Note: Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful during the calculations.
Example 1:
Input: word = "aba"
Output: 6
Explanation:
All possible substrings are: "a", "ab", "aba", "b", "ba", and "a".
- "b" has 0 vowels in it
- "a", "ab", "ba", and "a" have 1 vowel each
- "aba" has 2 vowels in it
Hence, the total sum of vowels = 0 + 1 + 1 + 1 + 1 + 2 = 6.
Example 2:
Input: word = "abc"
Output: 3
Explanation:
All possible substrings are: "a", "ab", "abc", "b", "bc", and "c".
- "a", "ab", and "abc" have 1 vowel each
- "b", "bc", and "c" have 0 vowels each
Hence, the total sum of vowels = 1 + 1 + 1 + 0 + 0 + 0 = 3.
Example 3:
Input: word = "ltcd"
Output: 0
Explanation: There are no vowels in any substring of "ltcd".
## Solution (C++)
```c=
class Solution {
public:
bool check_vowel(char c){
if(c=='a' || c=='e' || c=='i' || c=='o' || c=='u')
return true;
else
return false;
}
long long countVowels(string word) {
long long count = 0; long long ans = 0; long long prev = 0;
for(int i=0; i<word.length(); i++){
if(check_vowel(word[i])){
prev++;
}
count+=prev;
}
ans+=count;
for(int i=1; i<word.length(); i++){
if(check_vowel(word[i-1])){
count = count - (word.length()-i+1);
}
ans+=count;
}
return ans;
}
};
```
## Notes
* 先算出從index-0開頭的母音數量
* index-1到最後就不需要重複計算了，只需要判斷前一個index是否為母音，若是的話則減掉前一個index substring的數量。
* 有點sliding window的味道。
---
## 2958. Length of Longest Subarray With at Most K Frequency
```cpp=
class Solution {
public:
int maxSubarrayLength(vector<int>& nums, int k) {
int start = 0, end = 0;
map<int, int> record;
int max_length = 0;
for(end = 0; end<nums.size();){
record[nums[end]]++;
if(record[nums[end]] > k){
record[nums[start]]--;
record[nums[end]]--;
start++;
}
else{
if((end-start+1) > max_length){
max_length = (end-start+1);
}
end++;
}
}
return max_length;
}
};
```
### Notes:
1. 每一次的iteration，檢查record[nums[i]]有沒有超出限制
2. 若有則start++，沒有則end++(表示sliding window size增加)
---
## 2962. Count Subarrays Where Max Element Appears at Least K Times
```cpp=
class Solution {
public:
long long countSubarrays(vector<int>& nums, int k) {
long long ans = 0;
int start = 0, end = 0;
int max_element = 0;
int max_count = 0;
//find max element
for(int num: nums){
if(num > max_element)
max_element = num;
}
for(end = 0; end < nums.size();){
if(nums[end] == max_element)
max_count++;
if(max_count >= k){
ans = (long long)(ans + (nums.size() - end));
if(start == end){
start++;
end++;
max_count = 0;
}
else{
if(nums[start]==max_element)
max_count--;
max_count--;
start++;
}
}
else{
end++;
}
}
return ans;
}
};
```
### Notes:
1. 先找出max_element
2. 動態決定sliding window的大小，若目前window裡面的max element frequency < k，則window往右邊增加
3. 若frequency >= k，則計算結果，並將window往內縮(start++)
Sign in with Wallet
Connect another wallet