# LeetCode Minimum Window Substring

76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"


Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

hard题，用双指针+滑动窗口。核心思想是找到滑动窗口[i,j)，首先++j，加入右边界的字符；然后检查[i,j)是否能覆盖t；再然后++i，丢掉左边界的字符。

class Solution {
public:
string minWindow(string s, string t) {
int m = s.size(), n = t.size();
vector<int> required(128, 0);
for (int i = 0; i < n; ++i) {
++required[t[i]];
}

int min_len = m + 1, start_id = 0, found = 0;
int i = 0, j = 0;
while (j < m) {
--required[s[j]];
if (required[s[j]] >= 0) { // s[j]在t中
++found;
}
++j;

while (found == n) {
int cur_len = j - i;
if (cur_len < min_len) {
min_len = cur_len;
start_id = i;
}
++required[s[i]];
if (required[s[i]] > 0) --found;
++i;
}
}
if (min_len == m + 1) return "";
else return s.substr(start_id, min_len);
}
};

# LeetCode Maximum Number of Vowels in a Substring of Given Length

5417. Maximum Number of Vowels in a Substring of Given Length

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, 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.


Example 4:

Input: s = "rhythms", k = 4
Output: 0
Explanation: We can see that s doesn't have any vowel letters.


Example 5:

Input: s = "tryhard", k = 4
Output: 1


Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.
• 1 <= k <= s.length

class Solution {
public:
bool IsVol(const char &c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int maxVowels(string s, int k) {
int ans = 0;
int i = 0, j = k - 1, n = s.size();
for (int k = i; k <= j; ++k) {
if (IsVol(s[k]))++ans;
}
int cur = ans;
while (j < n - 1) {
++j;
if (IsVol(s[j]))++cur;
if (IsVol(s[i]))--cur;
++i;
ans = max(ans, cur);
}
return ans;
}
};

# LeetCode Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Given an array of integers nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to limit.

In case there is no subarray satisfying the given condition return 0.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2
Explanation: All subarrays are:
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4.
Therefore, the size of the longest subarray is 2.


Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.


Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3


Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= limit <= 10^9

class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
int n = nums.size();
int ans = 1; // 最小值是1

for (int i = 0; i < n; ++i) {
vector<int> dp_max(n, 0), dp_min(n, INT_MAX);
dp_max[i] = dp_min[i] = nums[i];
for (int len = 2; len <= n; ++len) {
int j = i + len - 1;
if (j >= n)break;
dp_max[j] = max(dp_max[j - 1], nums[j]);
dp_min[j] = min(dp_min[j - 1], nums[j]);
int diff = dp_max[j] - dp_min[j];
if (diff <= limit) {
ans = max(ans, j - i + 1);
}
else {
break;
}
}
}
return ans;
}
};

class Solution {
public:
int longestSubarray(vector<int>& A, int limit) {
int res = 0, n = A.size(), i = 0, j;
multiset<int> m;
for (j = 0; j < n; ++j) {
m.insert(A[j]);
if (*m.rbegin() - *m.begin() > limit)
m.erase(m.find(A[i++]));
else
res=max(res,j-i+1);
}
return res;
}
};

# LeetCode Maximum Points You Can Obtain from Cards

1423. Maximum Points You Can Obtain from Cards

There are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.


Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.


Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.


Example 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1.


Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202


Constraints:

• 1 <= cardPoints.length <= 10^5
• 1 <= cardPoints[i] <= 10^4
• 1 <= k <= cardPoints.length

class Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
int sum = 0, n = cardPoints.size();
for (int i = 0; i < n; ++i)sum += cardPoints[i];
if (k == n)return sum;

int min_window_sum = 0, i = 0, j = n - k - 1;
for (int k = i; k <= j; ++k)min_window_sum += cardPoints[k];
int cur_window_sum = min_window_sum;
while (j < n) {
if (j == n - 1)break;
cur_window_sum = cur_window_sum + cardPoints[++j] - cardPoints[i++];
min_window_sum = min(min_window_sum, cur_window_sum);
}
return sum - min_window_sum;
}
};

# LeetCode Maximum Average Subarray I

LeetCode Maximum Average Subarray I Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value. Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:
1. 1 <= k <= n <= 30,000.
2. Elements of the given array will be in the range [-10,000, 10,000].

# LeetCode Contains Duplicate III

220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true


Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true


Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3 Output: false

typedef long long ll;
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t)
{
set<ll> window;
for (int i = 0; i < nums.size(); ++i) {
if (i > k)
window.erase(nums[i – k – 1]); // 删除窗口左边的元素
auto it = window.lower_bound(ll(nums[i]) – t); // x>=nums[i]-t
if (it != window.end() && *it – nums[i] <= t)
return true; // x<=nums[i]+t
window.insert(nums[i]);
}
return false;
}
};

# LeetCode Longest Repeating Character Replacement

LeetCode Longest Repeating Character Replacement Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations. Note: Both the string’s length and k will not exceed 104. 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.

# LeetCode Permutation in String

LeetCode Permutation in String Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string. Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:
Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:
1. The input strings only contain lower case letters.
2. The length of both given strings is in range [1, 10,000].

# LeetCode Contains Duplicate II

219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true


Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true


Example 3:

Input: nums = [1,2,3,1,2,3], k = 2 Output: false

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
if (nums.size() == 0)
return false;
unordered_map<int, int> hash_table;
int distinct_cnt = 1; // 相异元素的个数
vector<vector<int> > duplicate_indices = { {} }; // 跳过第0个桶
for (int i = 0; i < nums.size(); i++) {
if (hash_table[nums[i]] == 0) {
hash_table[nums[i]] = distinct_cnt++;
duplicate_indices.push_back({ i });
}
else {
duplicate_indices[hash_table[nums[i]]].push_back(i);
// 把相同元素的下标都放到一个桶里
}
}
for (int i = 1; i < duplicate_indices.size(); i++) {
// 查每个桶
if (duplicate_indices[i].size() < 2)
continue;
for (int u = 0; u < duplicate_indices[i].size() – 1; u++) {
for (int v = u + 1; v < duplicate_indices[i].size(); v++) {
if (duplicate_indices[i][v] – duplicate_indices[i][u] <= k)
return true;
}
}
}
return false;
}
};

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
if (nums.size() == 0 || k <= 0)
return false;
if (k >= nums.size())
k = nums.size() – 1;
unordered_set<int> hash_set;
for (int i = 0; i < nums.size(); i++) {
if (i > k)
hash_set.erase(nums[i – k – 1]); // 滑动窗口，删掉窗口第一个元素
if (hash_set.find(nums[i]) != hash_set.end())
return true;
hash_set.insert(nums[i]); // 把新元素插入窗口
}
return false;
}
};

class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_map<int, int> hash;
for (int i = 0; i < nums.size(); ++i) {
if (hash.find(nums[i]) != hash.end() && i – hash[nums[i]] <= k)
return true;
hash[nums[i]] = i;
}
return false;
}
};