1
Input: s = "leetcode"
2
Output: 2
3
Explanation: The substring "ee" is of length 2 with the character 'e' only.

1
Input: s = "abbcccddddeeeeedcba"
2
Output: 5
3
Explanation: The substring "eeeee" is of length 5 with the character 'e' only.

1
class Solution:
2
    def maxPower(self, s: str) -> int:
3
        ans = 0
4
        l = 0
5
        cnt = defaultdict(int)
6
        for r, c in enumerate(s):
7
            cnt[c] += 1
8
            while len(cnt) > 1:
9
                cnt[s[l]] -= 1
10
                if cnt[s[l]] == 0: #因为你的check条件是size，所以当这个map中的某个元素的个数为0，要把它移出，不移除会让这个check条件一直符合，最终会让l一直++，到最后会超过s的长度，导致溢出。
11
                    del cnt[s[l]]
12
                l += 1
13
            ans = max(ans, r - l + 1)
14
        return ans

1
class Solution {
2
public:
3
    int maxPower(string s) {
4
        int ans = 0;
5
        int l = 0;
6
        int n = s.size();
7
        map<char, int> cnt;
8
        for (int r = 0; r < n; r++) {
9
            cnt[s[r]]++;
10
            while (cnt.size() > 1) {
11
                cnt[s[l]]--;
12
                if (cnt[s[l]] == 0) {
13
                    cnt.erase(s[l]);
14
                }
15
                l++;
16
            }
17
            ans = max(ans, r - l + 1);
18
        }
19
        return ans;
20
    }
21
};

1
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
2
Output: 6
3
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
4
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

1
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
2
Output: 10
3
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
4
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

1
class Solution:
2
    def longestOnes(self, nums: List[int], k: int) -> int:
3
        ans = 0
4
        l = 0
5
        cnt = 0
6
        for r, x in enumerate(nums):
7
            cnt += int(not x)
8
            while cnt > k:
9
                cnt -= int(not nums[l])
10
                l += 1
11
            ans = max(ans, r - l + 1)
12
        return ans

1
class Solution {
2
public:
3
    int longestOnes(vector<int>& nums, int k) {
4
        // you can flip at most k 0, it means the window has at most k zero, it can be 0, 1, to k.
5
        int ans = 0;
6
        int cnt = 0;
7
        int l = 0;
8
        int n = nums.size();
9
        for (int r = 0; r < n; r++) {
10
            // accumulate the amount of zero
11
            cnt += !nums[r];
12
            while (cnt > k) {
13
                cnt -= !nums[l];
14
                l++;
15
            }
16
            ans = max(ans, r - l + 1);
17
        }
18
        return ans;
19
    }
20
};

1
Input: s = "eceba", k = 2
2
Output: 3
3
Explanation: T is "ece" which its length is 3.

1
Input: s = "aa", k = 1
2
Output: 2
3
Explanation: T is "aa" which its length is 2.

1
class Solution {
2
public:
3
    int lengthOfLongestSubstringKDistinct(string s, int k) {
4
        int ans = 0;
5
        map<char, int> cnt;
6
        int l = 0;
7
        int n = s.size();
8
        for (int r = 0; r < n; r++) {
9
            cnt[s[r]]++;
10
            while (cnt.size() > k) {
11
                cnt[s[l]]--;
12
                if (cnt[s[l]] == 0) {
13
                    cnt.erase(s[l]);
14
                }
15
                l++;
16
            }
17
            ans = max(ans, r - l + 1);
18
        }
19
        return ans;
20
    }
21
};

1
class Solution:
2
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
3
        ans = 0
4
        cnt = defaultdict(int)
5
        l = 0
6
        for r, c in enumerate(s):
7
            cnt[c] += 1 # cnt[c] is an integer (the frequency of character c)
8
            while len(cnt) > k: // we need check how many distinct characters are currently in the sliding window.
9
                cnt[s[l]] -= 1
10
                if cnt[s[l]] == 0:
11
                    del cnt[s[l]]
12
                l += 1
13
            ans = max(ans, r - l + 1)
14
        return ans

1
Input: fruits = [1,2,1]
2
Output: 3
3
Explanation: We can pick from all 3 trees.

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

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

1
class Solution {
2
public:
3
    int totalFruit(vector<int>& fruits) {
4
        int ans = 0;
5
        map<int, int> cnt; // count each fruit type inside the window
6
        int l = 0;
7
        int n = fruits.size();
8
        for (int r = 0; r < n; r++) {
9
            cnt[fruits[r]]++; // do increment
10
            while (cnt.size() > 2) { // if the size of the fruit type exceed 2, we need shrink the window from the left
11
                cnt[fruits[l]]--;
12
                if (cnt[fruits[l]] == 0) {
13
                    cnt.erase(fruits[l]);
14
                }
15
                l++;
16
            }
17
            ans = max(ans, r - l + 1);
18
        }
19
        return ans;
20
    }
21
};

1
class Solution:
2
    def totalFruit(self, fruits: List[int]) -> int:
3
        ans = 0
4
        cnt = defaultdict(int)
5
        l = 0
6
        for r, x in enumerate(fruits):
7
            cnt[x] += 1
8
            while len(cnt) > 2: # reflects number of fruit types
9
                cnt[fruits[l]] -= 1
10
                if cnt[fruits[l]] == 0:
11
                    del cnt[fruits[l]]
12
                l += 1
13
            ans = max(ans, r - l + 1)
14
        return ans

1
Input: s = "abcabcbb"
2
Output: 3
3
Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.

1
Input: s = "bbbbb"
2
Output: 1
3
Explanation: The answer is "b", with the length of 1.

1
Input: s = "pwwkew"
2
Output: 3
3
Explanation: The answer is "wke", with the length of 3.
4
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

1
class Solution {
2
public:
3
    int lengthOfLongestSubstring(string s) {
4
        int ans = 0;
5
        int l = 0; // l is leftbound and r is right bound
6
        map<char, int> cnt;
7
        int n = s.size();
8
        for (int r = 0; r < n; r++) {
9
            cnt[s[r]]++;
10

11
            // if the occurrences of the current character is greater than one, it is not valid substring, we need shrink the left boundary to make it valid
12
            while (cnt[s[r]] > 1) {
13
                cnt[s[l]]--;
14
                if (cnt[s[l]] == 0) {
15
                    cnt.erase(s[l]);
16
                }
17
                l++;
18
            }
19
            ans = max(ans, r - l + 1);
20

21
        }
22
        return ans;
23
    }
24
};

1
class Solution:
2
    def lengthOfLongestSubstring(self, s: str) -> int:
3
        ans = 0
4
        l = 0
5
        cnt = defaultdict(int)
6
        for r, c in enumerate(s):
7
            cnt[c] += 1
8
            while cnt[c] > 1:
9
                cnt[s[l]] -= 1
10
                l += 1
11
            ans = max(ans, r - l + 1)
12
        return ans

1
class Solution {
2
public:
3
    int maximumLengthSubstring(string s) {
4
        int ans = 0;
5
        map<char, int> cnt;
6
        int l = 0;
7
        int n = s.size();
8
        for (int r = 0; r < n; r++) {
9
            cnt[s[r]]++;
10
            while (cnt[s[r]] > 2) { // if the count exceed 2, the window becomes invalid. we will shrink the window from the left
11
                cnt[s[l]]--; // decreses the count of s[l]
12
                l++; // move the left boundary to next position
13
            }
14
            ans = max(ans, r - l + 1);
15
        }
16
        return ans;
17
    }
18
};

1
class Solution:
2
    def maximumLengthSubstring(self, s: str) -> int:
3
        ans = 0
4
        d = defaultdict(int)
5
        l = 0
6
        for r, c in enumerate(s):
7
            d[c] += 1
8
            while d[c] > 2:
9
                d[s[l]] -= 1
10
                l += 1
11
            ans = max(ans, r - l + 1)
12
        return ans

1
Input: nums = [1,1,2,1,1], k = 3
2
Output: 2
3
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

1
Input: nums = [2,4,6], k = 1
2
Output: 0
3
Explanation: There are no odd numbers in the array.

1
Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
2
Output: 16

1
class Solution {
2
public:
3
    int numberOfSubarrays(vector<int>& nums, int k) {
4
        return atMostNumberOfSubarrays(nums, k)
5
            - atMostNumberOfSubarrays(nums, k - 1);
6

7
    }
8

9
private:
10
    int atMostNumberOfSubarrays(vector<int>& nums, int k) {
11
        int ans = 0;
12
        int oddCnt = 0;
13
        int left = 0;
14
        int n = nums.size();
15
        for (int right = 0; right < n; right++) {
16
            oddCnt += nums[right] & 1;
17
            while (oddCnt > k) {
18
                oddCnt -= nums[left] & 1;
19
                left++;
20
            }
21
            ans += right - left + 1;
22
        }
23
        return ans;
24
    }
25
};

1
# Why exactly K cannot be handled directly with a sliding window
2
# Imagine the current window contains exactly k odd numbers.
3
# When the right pointer moves:
4
# If the new number is odd → the count becomes k + 1 (invalid)
5
# If the new number is even → the count stays k (still valid)
6
# When the left pointer moves:
7
# If the removed number is odd → the count becomes k − 1 (invalid)
8
# If the removed number is even → the count stays k (still valid)
9
class Solution:
10
    """
11
    exactly K = at most K - at most (k - 1)
12
    """
13

14
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
15
        # This nested function exists only to help solve this problem.
16
        # share the context via closures
17
        def atMost(k):
18
            ans = l = cnt = 0
19
            for r, x in enumerate(nums):
20
                cnt += x & 1
21
                while cnt > k:
22
                    cnt -= nums[l] & 1
23
                    l += 1
24
                # when the while loop finishes, cnt must be less than or equal to k, it means the window [l, r] satisfies the constraint. so all subarrays ending at r and starting from any index between l and r are valid, so we add r - l + 1.
25
                ans += r - l + 1
26
            return ans
27

28
        # To compute the number of subarrays with exactly k odd numbers by using the numbers of subarrays with at most k odd numbers to substracting the one with at most k - 1 odd numbers.
29
        return atMost(k) - atMost(k - 1)

1
Input: word = "aeiouu"
2
Output: 2
3
Explanation: The vowel substrings of word are as follows (underlined):
4
- "aeiouu"
5
- "aeiouu"

1
Input: word = "unicornarihan"
2
Output: 0
3
Explanation: Not all 5 vowels are present, so there are no vowel substrings.

1
Input: word = "cuaieuouac"
2
Output: 7
3
Explanation: The vowel substrings of word are as follows (underlined):
4
- "cuaieuouac"
5
- "cuaieuouac"
6
- "cuaieuouac"
7
- "cuaieuouac"
8
- "cuaieuouac"
9
- "cuaieuouac"
10
- "cuaieuouac"

1
class Solution {
2
public:
3
    bool isVowel(char c) {
4
        return c == 'a' || c == 'e' || c == 'i'
5
            || c == 'o' || c == 'u';
6
    }
7

8
    int countVowelSubstrings(string word) {
9
        int ans = 0;
10
        int n = word.size();
11

12
        int i = 0;
13
        while (i < n) {
14
            if (!isVowel(word[i])) {
15
                i++;
16
                continue;
17
            }
18

19
            int j = i;
20
            while (j < n && isVowel(word[j])) j++;
21

22
            if (j - i >= 5) {
23
                unordered_map<char, int> cnt;
24
                int l = i;
25
                for (int r = i; r < j; r++) {
26
                    cnt[word[r]]++;
27
                    while (cnt.size() == 5) {
28
                        ans += j - r; // [l, r] is a valid substring, so [l, r], [l, r+1], [l, r+2], ..., [l, j-1] are also valid.
29

30
                        cnt[word[l]]--;
31
                        if (cnt[word[l]] == 0)
32
                            cnt.erase(word[l]);
33
                        l++;
34
                    }
35
                }
36
            }
37
            i = j;
38
        }
39

40
        return ans;
41
    }
42
};

1
class Solution:
2
    def countVowelSubstrings(self, word: str) -> int:
3
        ans = 0
4
        vowels = set('aeiou')
5
        i = 0
6
        while i < len(word):
7
            if word[i] not in vowels:
8
                i += 1
9
                continue
10
            j = i
11
            while j < len(word) and word[j] in vowels:
12
                j += 1
13
            if j - i >= len(vowels):
14
                cnt = defaultdict(int)
15
                l = i
16
                for r in range(i, j):
17
                    cnt[word[r]] += 1
18
                    while len(cnt) == len(vowels):
19
                        ans += j - r
20
                        cnt[word[l]] -= 1
21
                        if cnt[word[l]] == 0:
22
                            del cnt[word[l]]
23
                        l += 1
24
            i = j
25

26
        return ans

1
class Solution:
2
    def countVowelSubstrings(self, word: str) -> int:
3
        """
4
        当窗口 [l, r] 已经包含 a e i o u：
5
        [l, r]
6
        [l, r+1]
7
        [l, r+2]
8
        ……
9
        全部都是合法子串
10
        所以是 len(s) - r
11
        """
12
        ans = 0
13
        for s in re.findall(r'[aeiou]+', word):
14
            if len(s) < 5:
15
                continue
16
            cnt = defaultdict(int)
17
            l = 0
18
            for r, c in enumerate(s):
19
                cnt[c] += 1
20
                while len(cnt) == 5:
21
                    ans += len(s) - r
22
                    cnt[s[l]] -= 1
23
                    if cnt[s[l]] == 0:
24
                        del cnt[s[l]]
25
                    l += 1
26
        return ans

1
Input: nums = [1,2,1,2,3], k = 2
2
Output: 7
3
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

1
Input: nums = [1,2,1,3,4], k = 3
2
Output: 3
3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

1
class Solution {
2
public:
3
    int subarrayAtMostKDistinct(vector<int>& nums, int k) {
4
        int n = nums.size();
5
        int ans = 0;
6
        map<int, int>cnt;
7
        int l = 0;
8
        for (int r = 0; r < n; r++) {
9
            cnt[nums[r]]++;
10
            while (cnt.size() > k) { // distinc elements is greater than k
11
                cnt[nums[l]]--;
12
                if (cnt[nums[l]] == 0) {
13
                    cnt.erase(nums[l]);
14
                }
15
                l++;
16
            }
17
            /**
18
            [l, r] 中最多有 k 个不同元素
19

20
            [l, r]
21
            [l+1, r]
22
            [l+2, r]
23
            ...
24
            [r, r]
25

26
            r - l + 1 个
27
            **/
28
            ans += r - l + 1;
29
        }
30
        return ans;
31

32
    }
33
    int subarraysWithKDistinct(vector<int>& nums, int k) {
34
        return subarrayAtMostKDistinct(nums, k) - subarrayAtMostKDistinct(nums, k - 1);
35
    }
36
};

1
class Solution:
2
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
3
        def atMost(K):
4
            cnt = defaultdict(int)
5
            l = 0
6
            res = 0
7

8
            for r, x in enumerate(nums):
9
                cnt[x] += 1
10

11
                while len(cnt) > K:
12
                    cnt[nums[l]] -= 1
13
                    if cnt[nums[l]] == 0:
14
                        del cnt[nums[l]]
15
                    l += 1
16

17
                res += (r - l + 1)
18
            return res
19

20
        return atMost(k) - atMost(k - 1)