双指针与滑动窗口

def max_vowels(s: str, k: int) -> int:
    """Most vowels in any length-k substring (LC 1456)."""
    vowels = set("aeiou")
    cur = best = 0
    for i, c in enumerate(s):
        cur += c in vowels  # c enters the window
        if i >= k:
            cur -= s[i - k] in vowels  # s[i - k] leaves: the window is s[i-k+1..i]
        if i >= k - 1:  # only full windows count
            best = max(best, cur)
    return best

// Most vowels in any length-k substring (LC 1456).
int maxVowels(const string& s, int k) {
    auto vowel = [](char c) { return string("aeiou").find(c) != string::npos; };
    int cur = 0, best = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        cur += vowel(s[i]);  // s[i] enters the window
        if (i >= k) cur -= vowel(s[i - k]);  // s[i - k] leaves: the window is s[i-k+1..i]
        if (i >= k - 1) best = max(best, cur);  // only full windows count
    }
    return best;
}

class Solution {
    // Most vowels in any length-k substring (LC 1456).
    int maxVowels(String s, int k) {
        int cur = 0, best = 0;
        for (int i = 0; i < s.length(); i++) {
            if (vowel(s.charAt(i))) cur++; // s[i] enters the window
            if (i >= k && vowel(s.charAt(i - k))) cur--; // s[i - k] leaves: the window is s[i-k+1..i]
            if (i >= k - 1) best = Math.max(best, cur); // only full windows count
        }
        return best;
    }

    private boolean vowel(char c) {
        return "aeiou".indexOf(c) >= 0;
    }
}

import "strings"

// maxVowels returns the most vowels in any length-k substring (LC 1456).
func maxVowels(s string, k int) int {
	vowel := func(c byte) int {
		if strings.IndexByte("aeiou", c) >= 0 {
			return 1
		}
		return 0
	}
	cur, best := 0, 0
	for i := 0; i < len(s); i++ {
		cur += vowel(s[i]) // s[i] enters the window
		if i >= k {
			cur -= vowel(s[i-k]) // s[i - k] leaves: the window is s[i-k+1..i]
		}
		if i >= k-1 { // only full windows count
			best = max(best, cur)
		}
	}
	return best
}

def max_area(height: list[int]) -> int:
    """Most water two walls can hold (LC 11)."""
    lo, hi = 0, len(height) - 1
    best = 0
    while lo < hi:
        best = max(best, (hi - lo) * min(height[lo], height[hi]))
        if height[lo] < height[hi]:  # the shorter wall caps every narrower pair it is in
            lo += 1
        else:
            hi -= 1
    return best

// Most water two walls can hold (LC 11).
long long maxArea(const vector<int>& height) {
    int lo = 0, hi = (int)height.size() - 1;
    long long best = 0;
    while (lo < hi) {
        best = max(best, (long long)(hi - lo) * min(height[lo], height[hi]));
        if (height[lo] < height[hi]) lo++;  // the shorter wall caps every narrower pair it is in
        else hi--;
    }
    return best;
}

class Solution {
    // Most water two walls can hold (LC 11).
    long maxArea(int[] height) {
        int lo = 0, hi = height.length - 1;
        long best = 0;
        while (lo < hi) {
            best = Math.max(best, (long) (hi - lo) * Math.min(height[lo], height[hi]));
            if (height[lo] < height[hi]) lo++; // the shorter wall caps every narrower pair it is in
            else hi--;
        }
        return best;
    }
}

// maxArea returns the most water two walls can hold (LC 11).
func maxArea(height []int) int {
	lo, hi := 0, len(height)-1
	best := 0
	for lo < hi {
		best = max(best, (hi-lo)*min(height[lo], height[hi]))
		if height[lo] < height[hi] { // the shorter wall caps every narrower pair it is in
			lo++
		} else {
			hi--
		}
	}
	return best
}

from collections import defaultdict


def subarrays_with_k_distinct(nums: list[int], k: int) -> int:
    """Subarrays with exactly k distinct values (LC 992)."""

    def at_most(k: int) -> int:  # subarrays with at most k distinct values
        cnt = defaultdict(int)
        left = total = 0
        for right, x in enumerate(nums):
            cnt[x] += 1
            if cnt[x] == 1:
                k -= 1
            while k < 0:  # one distinct value too many: shrink from the left
                cnt[nums[left]] -= 1
                if cnt[nums[left]] == 0:
                    k += 1
                left += 1
            total += right - left + 1  # windows that end at right and start at or after left
        return total

    return at_most(k) - at_most(k - 1)

// Subarrays with exactly k distinct values (LC 992).
long long subarraysWithKDistinct(const vector<int>& nums, int k) {
    auto atMost = [&](int k) {  // subarrays with at most k distinct values
        unordered_map<int, int> cnt;
        long long total = 0;
        for (int left = 0, right = 0; right < (int)nums.size(); right++) {
            if (++cnt[nums[right]] == 1) k--;
            while (k < 0)  // one distinct value too many: shrink from the left
                if (--cnt[nums[left++]] == 0) k++;
            total += right - left + 1;  // windows that end at right and start at or after left
        }
        return total;
    };
    return atMost(k) - atMost(k - 1);
}

class Solution {
    // Subarrays with exactly k distinct values (LC 992).
    long subarraysWithKDistinct(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    // Subarrays with at most k distinct values.
    private long atMost(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        long total = 0;
        for (int left = 0, right = 0; right < nums.length; right++) {
            if (cnt.merge(nums[right], 1, Integer::sum) == 1) k--;
            while (k < 0) // one distinct value too many: shrink from the left
                if (cnt.merge(nums[left++], -1, Integer::sum) == 0) k++;
            total += right - left + 1; // windows that end at right and start at or after left
        }
        return total;
    }
}

// subarraysWithKDistinct counts the subarrays with exactly k distinct values (LC 992).
func subarraysWithKDistinct(nums []int, k int) int {
	atMost := func(k int) int { // subarrays with at most k distinct values
		cnt := map[int]int{}
		left, total := 0, 0
		for right, x := range nums {
			cnt[x]++
			if cnt[x] == 1 {
				k--
			}
			for k < 0 { // one distinct value too many: shrink from the left
				cnt[nums[left]]--
				if cnt[nums[left]] == 0 {
					k++
				}
				left++
			}
			total += right - left + 1 // windows that end at right and start at or after left
		}
		return total
	}
	return atMost(k) - atMost(k-1)
}