# Python Universal Template
def sliding_window(s, condition):
    # Initialize window state
    left = 0
    window_state = {}  # or Counter, set, etc.
    result = initialize_result()
    
    # Expand window with right pointer
    for right in range(len(s)):
        # Add current element to window
        update_window_state(s[right])
        
        # Contract window while invalid
        while not is_valid(window_state):
            # Remove leftmost element
            remove_from_window(s[left])
            left += 1
        
        # Update result with current valid window
        result = update_result(result, left, right)
    
    return result

// Java Universal Template  
public ResultType slidingWindow(String s) {
    // Initialize window state
    int left = 0;
    Map<Character, Integer> window = new HashMap<>();
    ResultType result = initializeResult();
    
    // Expand window with right pointer
    for (int right = 0; right < s.length(); right++) {
        char rightChar = s.charAt(right);
        window.put(rightChar, window.getOrDefault(rightChar, 0) + 1);
        
        // Contract window while invalid
        while (!isValid(window)) {
            char leftChar = s.charAt(left);
            window.put(leftChar, window.get(leftChar) - 1);
            if (window.get(leftChar) == 0) {
                window.remove(leftChar);
            }
            left++;
        }
        
        // Update result with current valid window
        result = updateResult(result, left, right);
    }
    
    return result;
}

# Fixed Size Window Template
def fixed_window(s, k):
    window = {}
    result = []
    
    for i in range(len(s)):
        # Add current element to window
        window[s[i]] = window.get(s[i], 0) + 1
        
        # Remove element that's outside window
        if i >= k:
            left_char = s[i - k]
            window[left_char] -= 1
            if window[left_char] == 0:
                del window[left_char]
        
        # Process window when it reaches target size
        if i >= k - 1:
            # Check condition and update result
            if meets_condition(window):
                result.append(i - k + 1)
    
    return result

// Fixed Size Window Template - Java
public List<Integer> fixedWindow(String s, int k) {
    Map<Character, Integer> window = new HashMap<>();
    List<Integer> result = new ArrayList<>();
    
    for (int i = 0; i < s.length(); i++) {
        // Add current element
        char cur = s.charAt(i);
        window.put(cur, window.getOrDefault(cur, 0) + 1);
        
        // Remove element outside window
        if (i >= k) {
            char leftChar = s.charAt(i - k);
            window.put(leftChar, window.get(leftChar) - 1);
            if (window.get(leftChar) == 0) {
                window.remove(leftChar);
            }
        }
        
        // Process when window is full
        if (i >= k - 1 && meetsCondition(window)) {
            result.add(i - k + 1);
        }
    }
    return result;
}

# Variable Size Window (Maximum) Template
def max_window(s):
    left = 0
    window = {}
    max_len = 0
    
    for right in range(len(s)):
        # Expand window
        window[s[right]] = window.get(s[right], 0) + 1
        
        # Contract while invalid
        while not is_valid(window):
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1
        
        # Update maximum length
        max_len = max(max_len, right - left + 1)
    
    return max_len

# Variable Size Window (Minimum) Template  
def min_window(s, target):
    left = 0
    window = {}
    target_count = Counter(target)
    min_len = float('inf')
    result = ""
    
    for right in range(len(s)):
        # Expand window
        window[s[right]] = window.get(s[right], 0) + 1
        
        # Contract while valid
        while is_valid(window, target_count):
            # Update minimum
            if right - left + 1 < min_len:
                min_len = right - left + 1
                result = s[left:right + 1]
            
            # Try to shrink
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1
    
    return result if min_len != float('inf') else ""

# Subarray Counting Template
def count_subarrays(nums, condition):
    left = 0
    count = 0
    window_state = initialize_state()
    
    for right in range(len(nums)):
        # Add current element
        update_window_state(nums[right])
        
        # Shrink window while invalid
        while not is_valid(window_state):
            remove_from_window(nums[left])
            left += 1
        
        # Count valid subarrays ending at 'right'
        count += right - left + 1

    return count

Exactly K = At Most K - At Most (K-1)

At Most K: All subarrays with ≤ K distinct/count
At Most (K-1): All subarrays with ≤ K-1 distinct/count

Difference: Only subarrays with EXACTLY K distinct/count

Array: [1, 2, 1, 2, 3]
K = 2 (exactly 2 distinct integers)

At Most 2 distinct:
[1], [1,2], [1,2,1], [1,2,1,2], [2], [2,1], [2,1,2], [1], [1,2], [2], [2,3], [3]
Count = 12

At Most 1 distinct:
[1], [2], [1], [2], [3]
Count = 5

Exactly 2 distinct = 12 - 5 = 7 ✓
[1,2], [1,2,1], [1,2,1,2], [2,1], [2,1,2], [1,2], [2,3]

# Universal At Most K Template
def at_most_k(nums, k):
    """
    Count subarrays with AT MOST K distinct/elements/condition.

    Time: O(n)
    Space: O(k) for tracking state

    Key: Window is valid when condition ≤ k
    """
    left = 0
    count = 0
    window_map = {}  # Track state (frequency, distinct, etc.)

    for right in range(len(nums)):
        # Expand window: add nums[right]
        window_map[nums[right]] = window_map.get(nums[right], 0) + 1

        # Shrink window while invalid (> k)
        while len(window_map) > k:  # Or other condition > k
            window_map[nums[left]] -= 1
            if window_map[nums[left]] == 0:
                del window_map[nums[left]]
            left += 1

        # Count all valid subarrays ending at 'right'
        # All subarrays from [left, right], [left+1, right], ..., [right, right]
        count += right - left + 1

    return count

# Transform to Exactly K
def exactly_k(nums, k):
    """
    Count subarrays with EXACTLY K distinct/elements/condition.

    Time: O(n) - at_most_k called twice
    Space: O(k)
    """
    if k == 0:
        return 0

    # Exactly K = At Most K - At Most (K-1)
    return at_most_k(nums, k) - at_most_k(nums, k - 1)

# Python - LC 992 Subarrays with K Different Integers
def subarraysWithKDistinct(nums, k):
    """
    Count subarrays with exactly K distinct integers.

    Time: O(n)
    Space: O(k)

    Key: Use Exactly K = At Most K - At Most (K-1) transformation
    """
    def at_most_k_distinct(k):
        """Count subarrays with at most K distinct integers."""
        left = 0
        count = 0
        freq = {}

        for right in range(len(nums)):
            # Add right element
            freq[nums[right]] = freq.get(nums[right], 0) + 1

            # Shrink while > k distinct
            while len(freq) > k:
                freq[nums[left]] -= 1
                if freq[nums[left]] == 0:
                    del freq[nums[left]]
                left += 1

            # Count subarrays ending at right
            count += right - left + 1

        return count

    # Edge case
    if k == 0:
        return 0

    # Exactly K = At Most K - At Most (K-1)
    return at_most_k_distinct(k) - at_most_k_distinct(k - 1)

# Example:
# nums = [1,2,1,2,3], k = 2
# at_most_k(2) = 12
# at_most_k(1) = 5
# exactly_k(2) = 12 - 5 = 7 ✓

// Java - LC 992 Subarrays with K Different Integers
/**
 * time = O(N)
 * space = O(K)
 */
public int subarraysWithKDistinct(int[] nums, int k) {
    // Exactly K = At Most K - At Most (K-1)
    return atMostK(nums, k) - atMostK(nums, k - 1);
}

private int atMostK(int[] nums, int k) {
    if (k == 0) return 0;

    int left = 0;
    int count = 0;
    Map<Integer, Integer> freq = new HashMap<>();

    for (int right = 0; right < nums.length; right++) {
        // Add right element
        freq.put(nums[right], freq.getOrDefault(nums[right], 0) + 1);

        // Shrink while > k distinct
        while (freq.size() > k) {
            freq.put(nums[left], freq.get(nums[left]) - 1);
            if (freq.get(nums[left]) == 0) {
                freq.remove(nums[left]);
            }
            left++;
        }

        // Count subarrays ending at right
        count += right - left + 1;
    }

    return count;
}

Array: [1, 2, 1, 3], K = 2 (exactly 2 distinct)

At Most 2 Distinct:
Index 0 (1): [1] ✓                                 → count = 1
Index 1 (2): [2] ✓, [1,2] ✓                        → count = 2
Index 2 (1): [1] ✓, [2,1] ✓, [1,2,1] ✓             → count = 3
Index 3 (3): [3] ✓, [1,3] ✓, but NOT [2,1,3] ❌    → count = 2
                   (window shrinks to [1,3])

Total At Most 2: 1 + 2 + 3 + 2 = 8

At Most 1 Distinct:
Index 0 (1): [1] ✓                                 → count = 1
Index 1 (2): [2] ✓, but NOT [1,2] ❌               → count = 1
                   (window shrinks to [2])
Index 2 (1): [1] ✓, but NOT [2,1] ❌               → count = 1
                   (window shrinks to [1])
Index 3 (3): [3] ✓, but NOT [1,3] ❌               → count = 1
                   (window shrinks to [3])

Total At Most 1: 1 + 1 + 1 + 1 = 4

Exactly 2 Distinct = 8 - 4 = 4 ✓

The 4 subarrays with exactly 2 distinct:
[1,2], [1,2,1], [2,1], [1,3]

✅ "exactly K distinct/different"
✅ "exactly K times"
✅ "exactly K occurrences"
✅ "subarrays with exactly K ..."
✅ COUNTING problems (not max/min length)

✅ "at most K"
✅ "maximum length with ≤ K"
✅ "minimum length with ≥ K"
✅ "longest substring with at most K"

# Wrong: Doesn't handle k=0
def exactly_k(nums, k):
    return at_most_k(nums, k) - at_most_k(nums, k - 1)
    # at_most_k(nums, -1) may fail!

# Right: Handle k=0 explicitly
def exactly_k(nums, k):
    if k == 0:
        return 0
    return at_most_k(nums, k) - at_most_k(nums, k - 1)

# Wrong: Using "exactly K" transformation for max length
def longest_k_distinct(s, k):
    # This gives COUNT, not LENGTH!
    return at_most_k(s, k) - at_most_k(s, k - 1)  ❌

# Right: Direct at_most_k for max length
def longest_k_distinct(s, k):
    # Track max window size during at_most_k
    return at_most_k_max_length(s, k)  ✓

# For COUNTING subarrays: use right - left + 1
count += right - left + 1

# For MAX LENGTH: track max window size
max_length = max(max_length, right - left + 1)

Interviewer: "Count subarrays with exactly K ..."
→ Think: "Exactly K = At Most K - At Most (K-1)"

Interviewer: "Find longest substring with at most K ..."
→ Think: "Direct sliding window, no subtraction needed"

Time: O(n) - each element added once, removed at most once in each pass
      Total: 2 passes × O(n) = O(n)

Space: O(k) - HashMap stores at most K distinct elements

def exactly_k(nums, k):
    def at_most_k(limit):
        left = 0
        count = 0
        window = {}

        for right in range(len(nums)):
            window[nums[right]] = window.get(nums[right], 0) + 1

            while len(window) > limit:
                window[nums[left]] -= 1
                if window[nums[left]] == 0:
                    del window[nums[left]]
                left += 1

            count += right - left + 1

        return count

    if k == 0:
        return 0
    return at_most_k(k) - at_most_k(k - 1)

# Naive attempt (WRONG!)
def exactly_k_direct(nums, k):
    left = 0
    count = 0
    window = {}

    for right in range(len(nums)):
        window[nums[right]] = window.get(nums[right], 0) + 1

        # When to shrink? This is tricky!
        # If len(window) > k: shrink (too many distinct)
        # If len(window) < k: can't count yet (too few distinct)
        # If len(window) == k: count, but should we shrink?

        # If we shrink when == k, we might miss valid subarrays
        # If we don't shrink, we might count invalid subarrays

        # There's no clean condition! ❌

    return count

# Window validity is monotonic:
# - If window is valid (≤ K), all sub-windows are valid
# - If window becomes invalid (> K), shrink until valid
# - Clear shrinking condition: while len(window) > k

# This monotonic property makes sliding window perfect!

Let S(k) = set of all subarrays with at most k distinct elements

S(2) = {[1], [1,2], [1,2,1], [2], [2,1], [1], [1,3], [3], ...}
S(1) = {[1], [2], [1], [3], ...}  (only single-element subarrays)

S(2) \ S(1) = subarrays in S(2) but not in S(1)
            = subarrays with MORE than 1 but AT MOST 2 distinct
            = subarrays with EXACTLY 2 distinct ✓

Generalized: S(k) \ S(k-1) = subarrays with exactly k distinct

nums = [2,2,1,2,1], k = 2

At r = 4 (last element), valid subarrays ending here:
  [1,2,1]           → starts at index 2
  [2,1,2,1]         → starts at index 1
  [2,2,1,2,1]       → starts at index 0

→ 3 valid left boundaries, but pure sliding window finds only 1!

When oddCount reaches k (window has exactly k odds):
  - Count how many even numbers are at the LEFT edge of the window
    before hitting the (k-th-from-left) odd number
  - Each of these even numbers gives one more valid left boundary
  - Store this count as `prefix`

After the window shrinks past the leftmost odd:
  - oddCount drops below k, so the while loop exits
  - But `prefix` (the "even gap") is PRESERVED
  - For every future r that keeps oddCount == k,
    those same left boundaries are still valid → add `prefix` again

// Prefix Trick + Sliding Window
// time = O(N), space = O(1)
public int exactlyK(int[] nums, int k) {
    int l = 0, res = 0, oddCount = 0, prefix = 0;

    for (int r = 0; r < nums.length; r++) {
        if (nums[r] % 2 == 1) {
            oddCount++;
            prefix = 0;  // reset: new odd changes left boundary gap
        }

        // Shrink left while window has exactly k odds,
        // counting even elements we skip at the left edge
        while (oddCount == k) {
            prefix++;                        // one more valid left boundary
            if (nums[l] % 2 == 1) oddCount--;
            l++;
        }

        // prefix = # of valid left boundaries for subarrays ending at r
        res += prefix;
    }

    return res;
}

r=0 (2): oddCount=0, prefix=0  → res=0
r=1 (2): oddCount=0, prefix=0  → res=0
r=2 (1): oddCount=1, prefix=0  → res=0   (new odd, prefix reset)
r=3 (2): oddCount=1, prefix=0  → res=0
r=4 (1): oddCount=2, prefix=0  → new odd, prefix reset to 0
  while oddCount==2:
    prefix=1, nums[0]=2 (even), l=1       → oddCount still 2
    prefix=2, nums[1]=2 (even), l=2       → oddCount still 2
    prefix=3, nums[2]=1 (odd),  l=3, oddCount=1 → exit while
  res += 3 → res=3

Problem Analysis Flowchart:

1. Is window size fixed?
   ├── YES → Use Fixed Size Template
   └── NO → Continue to 2

2. Are you finding maximum length?
   ├── YES → Use Variable Max Template  
   └── NO → Continue to 3

3. Are you finding minimum length?
   ├── YES → Use Variable Min Template
   └── NO → Continue to 4

4. Are you counting subarrays?
   ├── YES → Use Counting Template
   └── NO → Use custom approach

// java
// LC 567
    // V0
    // IDEA: HASHMAP + SLIDING WINDOW (fixed by gpt)
    public boolean checkInclusion(String s1, String s2) {
        if (!s1.isEmpty() && s2.isEmpty()) {
            return false;
        }
        if (s1.equals(s2)) {
            return true;
        }
        /** NOTE !!!
         *
         *  we init 2 map, one for s1 counter, the other one as track `s2 sub str counter`
         */
        Map<String, Integer> map1 = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();
        for (String x : s1.split("")) {
            String k = String.valueOf(x);
            map1.put(x, map1.getOrDefault(k, 0) + 1);
        }

        // 2 pointers (for s2)
        /** NOTE !!!
         *
         *  we have 2 pointers (for s2) that can track character cnt in s2 within l, r pointers
         */
        int l = 0;
        for (int r = 0; r < s2.length(); r++) {
            String val = String.valueOf(s2.charAt(r));
            map2.put(val, map2.getOrDefault(val, 0) + 1);

            /** NOTE !!!
             *
             *  we use below trick to
             *
             *  -> 1) check if `new reached s2 val` is in s1 map
             *  -> 2) check if 2 map are equal
             *
             *  -> so we have more simple code, and clean logic
             */
            if (map2.equals(map1)) {
                return true;
            }

            /**
             *  NOTE !!!
             *
             *  If the window size exceeds the size of s1, move the left pointer
             *  -> means the `permutation str in s2 of s1` IS NOT FOUND YET,
             *  -> in this case, we need to move s2 left pointer, and update tracking map
             */
            if ((r - l + 1) >= s1.length()) {
                // update map
                String leftVal = String.valueOf(s2.charAt(l));
                map2.put(leftVal, map2.get(leftVal) - 1);
                /**
                 * NOTE !!!
                 *
                 *  if can't find permutation at current window ([l,r]),
                 *  then we move left pointer 1 idx (e.g. l += 1)
                 *  for moving and checking next window
                 */
                l += 1;
                if (map2.get(leftVal) == 0) {
                    map2.remove(leftVal);
                }
            }
        }

        return false;
    }

# LC 567 Permutation in String
# V0 
import collections
class Solution(object):
    def checkInclusion(self, s1, s2):
        l1, l2 = len(s1), len(s2)
        c1 = collections.Counter(s1)
        c2 = collections.Counter()
        p = q = 0
        while q < l2:
            c2[s2[q]] += 1
            if c1 == c2:
                return True
            q += 1
            if q - p + 1 > l1:
                c2[s2[p]] -= 1
                if c2[s2[p]] == 0:
                    del c2[s2[p]]
                p += 1
        return False

// LC 438
    // V0
    // IDEA: HASHMAP + 2 POINTERS (fixed by gpt)
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        // edge
        if (s == null || p == null || s.isEmpty() || p.isEmpty() || p.length() > s.length()) {
            return res;
        }
        if (s.equals(p)) {
            res.add(0);
            return res;
        }

        // init p map
        Map<String, Integer> p_map = new HashMap<>();
        for (String x : p.split("")) {
            p_map.put(x, p_map.getOrDefault(x, 0) + 1);
        }

        String[] s_arr = s.split("");
        Map<String, Integer> s_map = new HashMap<>();

        int l = 0;
        for (int r = 0; r < s_arr.length; r++) {
            String key = s_arr[r];
            s_map.put(key, s_map.getOrDefault(key, 0) + 1);

            /**
             *  NOTE !!!
             *
             *   need `while loop` below
             *   so we can `shrink` left pointer (window)
             *   to make the sub string size equals to `p`
             *
             *   (could be `if` logic as well here)
             *   (e.g. if (r - l + 1 > p.length()) )
             */
            // shrink window if size > p.length()
            while (r - l + 1 > p.length()) {
                String leftKey = s_arr[l];
                /**
                 *  NOTE !!!
                 *
                 *   need to update s_map
                 */
                s_map.put(leftKey, s_map.get(leftKey) - 1);
                if (s_map.get(leftKey) == 0) {
                    s_map.remove(leftKey);
                }
                l++;
            }

            /**
             *  NOTE !!!
             *
             *  if same size, compare s_map, and p_map
             */
            // if same size, compare
            if (r - l + 1 == p.length() && isEqaual(p_map, s_map)) {
                res.add(l);
            }
        }

        return res;
    }

    private boolean isEqaual(Map<String, Integer> p_map, Map<String, Integer> s_map) {
        if (p_map.size() != s_map.size()) {
            return false;
        }
        for (String k : p_map.keySet()) {
            if (!s_map.containsKey(k) || !s_map.get(k).equals(p_map.get(k))) {
                return false;
            }
        }
        return true;
    }

    // V0-1
    // IDEA: HASHMAP + SLIDE WINDOW (gpt)
    /**
     *  Why `slide window` is needed trick for this problem?
     *
     *
     *  Yes 👍 the sliding window (or two-pointer) is the needed trick for that group of problems like “longest substring without repeating characters”.
     *
     * Here’s why:
     *  •   A brute force way would check all substrings → O(n²) or worse.
     *  •   But with a sliding window, you keep a “window” [left, right] over the string/array and expand right step by step.
     *  •   If the constraint is violated (like duplicate chars appear, or the sum is too large), you shrink from the left until it’s valid again.
     *  •   This way each index moves at most once → O(n) total.
     *
     * That’s the exact “trick” behind those problems. The hard part is usually:
     *  1.  What condition makes the window valid/invalid? (duplicate chars, sum > k, etc.)
     *  2.  When to update the answer? (on every valid window, or only when shrinking).
     *
     */
    public List<Integer> findAnagrams_0_1(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s == null || p == null || s.isEmpty() || p.isEmpty() || p.length() > s.length()) {
            return res;
        }

        // Build p_map (pattern frequency)
        Map<String, Integer> p_map = new HashMap<>();
        for (String x : p.split("")) {
            p_map.put(x, p_map.getOrDefault(x, 0) + 1);
        }

        Map<String, Integer> s_map = new HashMap<>();
        String[] s_arr = s.split("");
        int window = p.length();

        for (int i = 0; i < s_arr.length; i++) {
            String val = s_arr[i];

            /**  NOTE !!!
             *
             *  we `add` element to s_amp anyway,
             *  via `sliding window`  we DON'T need to handle cases
             *  such as 1) if the element in p_map, 2) if the element cnt > the one in p_map ...
             *
             *  -> via `sliding window`, we can simply ONLY compare
             *     if s_map and p_map qre equals when `sliding window` size equals to p size
             */
            // add current char to s_map
            s_map.put(val, s_map.getOrDefault(val, 0) + 1);

            /**  NOTE !!!
             *
             *  sliding window
             */
            // maintain sliding window size
            if (i >= window) {
                String leftChar = s_arr[i - window];
                if (s_map.get(leftChar) == 1) {
                    s_map.remove(leftChar);
                } else {
                    s_map.put(leftChar, s_map.get(leftChar) - 1);
                }
            }

            // compare maps only when window size matches
            if (i >= window - 1 && isEqual(p_map, s_map)) {
                res.add(i - window + 1);
            }
        }

        return res;
    }

    private boolean isEqual(Map<String, Integer> p_map, Map<String, Integer> s_map) {
        if (p_map.size() != s_map.size()) {
            return false;
        }
        for (String k : p_map.keySet()) {
            if (!s_map.containsKey(k) || !p_map.get(k).equals(s_map.get(k))) {
                return false;
            }
        }
        return true;
    }

# LC 438 Find All Anagrams in a String
# V0
# IDEA : SLIDING WINDOW + collections.Counter()
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        ls, lp = len(s), len(p)
        cp = collections.Counter(p)
        cs = collections.Counter()
        ans = []
        for i in range(ls):
            cs[s[i]] += 1
            if i >= lp:
                cs[s[i - lp]] -= 1
                ### BE AWARE OF IT
                if cs[s[i - lp]] == 0:
                    del cs[s[i - lp]]
            if cs == cp:
                ans.append(i - lp + 1)
        return ans

# LC 003 Longest Substring Without Repeating Characters
# V0'
# IDEA : SLIDING WINDOW + DICT
#       -> use a hash table (d) record visited "element" (e.g. : a,b,c,...)
#          (but NOT sub-string)
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        d = {}
        # left pointer
        l = 0
        res = 0
        # right pointer
        for r in range(len(s)):
            """
            ### NOTE : we deal with "s[r] in d" case first 
            ### NOTE : if already visited, means "repeating"
            #      -> then we need to update left pointer (l)
            """
            if s[r] in d:
                """
                NOTE !!! this
                -> via max(l, d[s[r]] + 1) trick,
                   we can get the "latest" idx of duplicated s[r], and start from that one
                """
                l = max(l, d[s[r]] + 1)
            # if not visited yet, record the alphabet
            # and re-calculate the max length
            d[s[r]] = r
            res = max(res, r -l + 1)
        return res

# V0'
# IDEA : SLIDING WINDOW + DICT
#       -> use a hash table (d) record visited "element" (e.g. : a,b,c,...)
#          (but NOT sub-string)
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        d = {}
        # left pointer
        l = 0
        res = 0
        # right pointer
        for r in range(len(s)):
            """
            ### NOTE : we deal with "s[r] in d" case first 
            ### NOTE : if already visited, means "repeating"
            #      -> then we need to update left pointer (l)
            """
            if s[r] in d:
                """
                NOTE !!! this
                -> via max(l, d[s[r]] + 1) trick,
                   we can get the "latest" idx of duplicated s[r], and start from that one
                """
                l = max(l, d[s[r]] + 1)
            # if not visited yet, record the alphabet
            # and re-calculate the max length
            d[s[r]] = r
            res = max(res, r -l + 1)
        return res

// java
// V0
// IDEA : SLIDING WINDOW + HASH SET
public int lengthOfLongestSubstring(String s) {

    if (s.equals("")){
        return 0;
    }

    if (s.equals(" ")){
        return 1;
    }

    if (s.length() == 1){
        return 1;
    }

    int ans = 0;
    char[] s_array = s.toCharArray();
    for (int i = 0; i < s_array.length-1; i++){
        int j = i;
        Set<String> set = new HashSet<String>();
        while (j < s_array.length){
            String cur = String.valueOf(s_array[j]);
            if (set.contains(cur)){
                ans = Math.max(ans, set.size());
                break;
            }else{
                set.add(cur);
                ans = Math.max(ans, set.size());
                j += 1;
            }
        }
    }

    return ans;
}

# LC 713 Subarray Product Less Than K
# V0 
# IDEA : SLIDING WINDOW 
# MAINTAIN 2 INDEX : left, i, SO THE SLIDING WINDOW IS : [left, i]
# CHECK IF THE PRODUCT OF ALL DIGITS IN THE WINDOW [left, i] < k
# IF NOT, REMOVE CURRENT LEFT, AND DO LEFT ++
# REPEAT ABOVE PROCESS AND GO THOROUGH ALL ARRAY  
class Solution:
    def numSubarrayProductLessThanK(self, nums, k):
        # init values
        product = 1
        i = 0
        result = 0
        
        for j, num in enumerate(nums):
            ### NOTE : we get product first
            product *= num
            ### NOTE : the while loop condition : product >= k
            #         -> if product >= k, we do the corresponding op
            while i <= j and product >= k:
                ### NOTE this trick
                #    -> divided the number back, since this number already make the product > k 
                product = product // nums[i]
                ### NOTE : move i to 1 right index
                i += 1
            ### NOTE : , the number of intervals with subarray product less than k and with right-most coordinate right, is right - left + 1
            #    -> https://leetcode.com/problems/subarray-product-less-than-k/solution/           
            result += (j - i + 1)           
        return result

# LC 209 Minimum Size Subarray Sum
# V0
# IDEA : SLIDING WINDOW : start, end
class Solution:
    def minSubArrayLen(self, s, nums):
        if nums is None or len(nums) == 0:
            return 0

        n = len(nums)
        minLength = n + 1
        sum = 0
        j = 0
        for i in range(n):
            ### NOTE the while loop condition (j < n and sum < s)
            while j < n and sum < s:
                sum += nums[j]
                j += 1
            # NOTE : we need to check if sum >= s here
            if sum >= s:
                minLength = min(minLength, j - i)

            ### NOTE : we need to get min length of sub array
            #          so once it meats the condition (sum >= s)
            #          we should update the minLength (minLength = min(minLength, j - i))
            #          and move to next i and roll back _sum (_sum -= nums[i])
            sum -= nums[i]
            
        ### NOTE : if minLength == n + 1, means there is no such subarray, so return 0 instead
        if minLength == n + 1:
            return 0         
        return minLength

# lc 424. Longest Repeating Character Replacement
# V0
# IDEA : SLIDING WINDOW + DICT + 2 POINTERS
from collections import Counter
class Solution(object):
    def characterReplacement(self, s, k):
        table = Counter()
        res = 0
        p1 = p2 = 0
        # below can be either while or for loop
        while p2 < len(s):
            table[s[p2]] += 1
            p2 += 1
            """
            ### NOTE : if remain elements > k, means there is no possibility to make this substring as "longest substring containing the same letter"
               ->  remain elements = p1 - p2 - max(table.values())
               ->  e.g. if we consider "max(table.values()" as the "repeating character", then "p2 - p1 - max(table.values()" is the count of elements we need to replace
               ->  so we need to clear "current candidate" for next iteration
            """
            while p2 - p1 - max(table.values()) > k:
                table[s[p1]] -= 1
                p1 += 1
            res = max(res, p2 - p1)
        return res
    
# V0'
from collections import defaultdict
class Solution:
    def characterReplacement(self, s, k):
        cnt = defaultdict(int)
        maxLen = 0
        l = 0
        # below can be either while or for loop
        for r in range(len(s)):
            cnt[s[r]] += 1
            ### NOTE : this condition
            while r - l + 1 - max(cnt.values()) > k:
                cnt[s[l]] -= 1
                l += 1
            maxLen = max(maxLen, r - l + 1)     

        return maxLen

// java
// LC 424
// V2
// IDEA : Sliding Window (Slow)
// https://leetcode.com/problems/longest-repeating-character-replacement/editorial/
public int characterReplacement_4(String s, int k) {
    HashSet<Character> allLetters = new HashSet();

    // collect all unique letters
    for (int i = 0; i < s.length(); i++) {
        allLetters.add(s.charAt(i));
    }

    int maxLength = 0;
    for (Character letter : allLetters) {
        int start = 0;
        int count = 0;
        // initialize a sliding window for each unique letter
        for (int end = 0; end < s.length(); end += 1) {
            if (s.charAt(end) == letter) {
                // if the letter matches, increase the count
                count += 1;
            }
            // bring start forward until the window is valid again
            while (!isWindowValid(start, end, count, k)) {
                if (s.charAt(start) == letter) {
                    // if the letter matches, decrease the count
                    count -= 1;
                }
                start += 1;
            }
            // at this point the window is valid, update maxLength
            maxLength = Math.max(maxLength, end + 1 - start);
        }
    }
    return maxLength;
}

private Boolean isWindowValid(int start, int end, int count, int k) {
    // end + 1 - start - count is different element count
    return end + 1 - start - count <= k;
}

# LC 413 Arithmetic Slices
# V0
# IDEA : SLIDING DINDOW + 2 pointers
# STEPS:
#   -> step 1) loop over nums from idx=2 (for i in range(2, len(A)))
#   -> step 2) use the other pointer j, "look back to idx = 0" via while loop
#       -> if there is any case fit condition, add to result
#   -> step 3) return ans
class Solution(object):
    def numberOfArithmeticSlices(self, A):
        # edge case
        if not A or len(A) < 3:
            return 0
        res = 0
        j = 2
        for i in range(2, len(A)):
            # use the other pointer j, "look back to idx = 0" via while loop
            j = i
            while j-2 >= 0:
                # if there is any case fit condition, add to result
                if A[j] - A[j-1] == A[j-1] - A[j-2]:
                    res += 1
                    j -= 1
                else:
                    break
        return res 

# LC 1151 Minimum Swaps to Group All 1's Together
# V0
# IDEA : Sliding Window with Two Pointers
# IDEA : core : Find which sub-array HAS MOST "1", since it means it needs MINIMUM SWAP for getting all "1" toogether
# https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together/solution/
class Solution:
    def minSwaps(self, data):
        ones = sum(data)
        cnt_one = max_one = 0
        left = right = 0
        while right < len(data):
            # updating the number of 1's by adding the new element
            cnt_one += data[right]
            right += 1
            # maintain the length of the window to ones
            if right - left > ones:
                # updating the number of 1's by removing the oldest element
                cnt_one -= data[left]
                left += 1
            # record the maximum number of 1's in the window
            max_one = max(max_one, cnt_one)
        return ones - max_one

// java
// LC 763 Partition Labels

// V0-2
// IDEA: GREEDY + hashMap record last idx + sliding window (fixed by gpt)
public List<Integer> partitionLabels_0_2(String s) {
    List<Integer> res = new ArrayList<>();

    if (s == null || s.length() == 0) {
        return res;
    }

    // Map each character to its last index
    Map<Character, Integer> lastIndexMap = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        lastIndexMap.put(s.charAt(i), i);
    }

    int l = 0;
    while (l < s.length()) {
        int end = lastIndexMap.get(s.charAt(l));
        int r = l;

        // Expand the window to include all characters in the current segment
        while (r < end) {
            end = Math.max(end, lastIndexMap.get(s.charAt(r)));
            r++;
        }

        res.add(end - l + 1);
        l = end + 1;
    }

    return res;
}

    public int maxFrequency_0_1(int[] nums, int k) {
        /**
         *
         * Sort nums in non-decreasing order.
         * Sorting is crucial — when array is sorted,
         * if we want to raise several elements
         * to match some target value,
         * the cheapest target to aim for is
         * always the current rightmost value in a sorted window.
         */
        Arrays.sort(nums); // sort ascending

        /**
         * Maintain the `sum of the current sliding window. `
         * Use long to prevent integer overflow
         * if nums values and window size are large.
         *
         *
         * -> windowSum: sum of cur slide window
         */
        long windowSum = 0; // use long to avoid overflow
        // left is the left index of the sliding window. res stores the best (maximum) window size found so far.
        // Initialize res = 1 because at least one element always fits.
        int left = 0;
        int res = 1;

        for (int right = 0; right < nums.length; right++) {
            windowSum += nums[right];

            /**
             *  NOTE !!! core logic:
             *
             *  This computes the cost to make every element in window [left..right] equal to nums[right]:
             *
             *   - nums[right] * windowSize is the total value
             *     if every element became nums[right].
             *   - Subtract windowSum (the current total) to
             *     get how much increment is needed.
             *
             * If this cost exceeds k, the current window is
             *  not achievable with at most k increments,
             *  so we must shrink it from the left.
             *
             *
             * Important: cast nums[right] to long (done by (long)) to avoid overflow in product.
             *
             */
            // cost to make all numbers in window [left..right] equal to nums[right]:
            // cost = nums[right] * windowSize - windowSum
            // if cost > k, shrink from the left
            /**  NOTE !!
             *
             *  nums[right] * (right - left + 1):  how much increment needed
             *
             */
            while ((long) nums[right] * (right - left + 1) - windowSum > k) {
                /**
                 * Remove the leftmost element from the window sum because we are going to increment left.
                 */
                windowSum -= nums[left];
                left++;
            }

            // update max length
            res = Math.max(res, right - left + 1);
        }

        return res;
    }

# Track character counts in window
window = {}
window[char] = window.get(char, 0) + 1

# Remove character from window
window[char] -= 1
if window[char] == 0:
    del window[char]

# Common validity checks
def is_valid_permutation(window, target):
    return window == target

def is_valid_distinct_k(window, k):
    return len(window) <= k

def is_valid_sum(current_sum, target):
    return current_sum >= target

# Maximum length problems
max_len = max(max_len, right - left + 1)

# Minimum length problems  
if is_valid:
    min_len = min(min_len, right - left + 1)

# Counting problems
count += right - left + 1  # All subarrays ending at 'right'

// LC 1004 - Max Consecutive Ones III
// IDEA: Sliding window — track zero count, shrink when zeroCnt > k
// time = O(N), space = O(1)
public int longestOnes(int[] nums, int k) {
    int l = 0, zeroCnt = 0, ans = 0;
    for (int r = 0; r < nums.length; r++) {
        if (nums[r] == 0) zeroCnt++;
        while (zeroCnt > k) {
            if (nums[l] == 0) zeroCnt--;
            l++;
        }
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}

// LC 3 - Longest Substring Without Repeating Characters
// IDEA: Sliding window with HashSet to track characters in window
// time = O(N), space = O(min(N, charset))
public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int l = 0, ans = 0;
    for (int r = 0; r < s.length(); r++) {
        while (set.contains(s.charAt(r))) {
            set.remove(s.charAt(l++));
        }
        set.add(s.charAt(r));
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}

// LC 76 - Minimum Window Substring
// IDEA: Sliding window with frequency maps; shrink when window is valid
// time = O(N + M), space = O(N + M)
public String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
    int l = 0, valid = 0, start = 0, minLen = Integer.MAX_VALUE;
    for (int r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        window.merge(c, 1, Integer::sum);
        if (need.containsKey(c) && window.get(c).equals(need.get(c))) valid++;
        while (valid == need.size()) {
            if (r - l + 1 < minLen) { minLen = r - l + 1; start = l; }
            char d = s.charAt(l++);
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) valid--;
                window.merge(d, -1, Integer::sum);
            }
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

// LC 567 - Permutation in String
// IDEA: Fixed sliding window — track char frequencies, check match
// time = O(N), space = O(1)
public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) return false;
    int[] need = new int[26], window = new int[26];
    for (char c : s1.toCharArray()) need[c-'a']++;
    int k = s1.length();
    for (int i = 0; i < s2.length(); i++) {
        window[s2.charAt(i)-'a']++;
        if (i >= k) window[s2.charAt(i-k)-'a']--;
        if (Arrays.equals(need, window)) return true;
    }
    return false;
}

// LC 438 - Find All Anagrams in a String
// IDEA: Fixed sliding window — collect all positions where window = anagram
// time = O(N), space = O(1)
public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (s.length() < p.length()) return result;
    int[] need = new int[26], window = new int[26];
    for (char c : p.toCharArray()) need[c-'a']++;
    int k = p.length();
    for (int i = 0; i < s.length(); i++) {
        window[s.charAt(i)-'a']++;
        if (i >= k) window[s.charAt(i-k)-'a']--;
        if (Arrays.equals(need, window)) result.add(i - k + 1);
    }
    return result;
}

// LC 209 - Minimum Size Subarray Sum
// IDEA: Sliding window — shrink left when sum >= target, record min length
// time = O(N), space = O(1)
public int minSubArrayLen(int target, int[] nums) {
    int l = 0, sum = 0, minLen = Integer.MAX_VALUE;
    for (int r = 0; r < nums.length; r++) {
        sum += nums[r];
        while (sum >= target) {
            minLen = Math.min(minLen, r - l + 1);
            sum -= nums[l++];
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

// LC 424 - Longest Repeating Character Replacement
// IDEA: Sliding window — valid if windowSize - maxFreq <= k
// time = O(N), space = O(1)
public int characterReplacement(String s, int k) {
    int[] freq = new int[26];
    int l = 0, maxFreq = 0, ans = 0;
    for (int r = 0; r < s.length(); r++) {
        freq[s.charAt(r)-'A']++;
        maxFreq = Math.max(maxFreq, freq[s.charAt(r)-'A']);
        while ((r - l + 1) - maxFreq > k) freq[s.charAt(l++)-'A']--;
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}

// LC 713 - Subarray Product Less Than K
// IDEA: Sliding window — count subarrays ending at r with product < k
// time = O(N), space = O(1)
public int numSubarrayProductLessThanK(int[] nums, int k) {
    if (k <= 1) return 0;
    int l = 0, product = 1, count = 0;
    for (int r = 0; r < nums.length; r++) {
        product *= nums[r];
        while (product >= k) product /= nums[l++];
        count += r - l + 1; // all subarrays ending at r with left in [l, r]
    }
    return count;
}

// LC 239 - Sliding Window Maximum
// IDEA: Monotonic decreasing deque — front = max of current window
// time = O(N), space = O(k)
public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] ans = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>(); // stores indices
    for (int i = 0; i < n; i++) {
        // remove out-of-window indices
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) deque.pollFirst();
        // maintain decreasing order
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
        deque.offerLast(i);
        if (i >= k - 1) ans[i - k + 1] = nums[deque.peekFirst()];
    }
    return ans;
}

// LC 1838 - Frequency of the Most Frequent Element
// IDEA: Sort + sliding window — equalize all elements in window to nums[r]
// time = O(N log N), space = O(1)
public int maxFrequency(int[] nums, int k) {
    Arrays.sort(nums);
    int l = 0, ans = 1;
    long windowSum = 0;
    for (int r = 1; r < nums.length; r++) {
        windowSum += nums[r];
        // cost to raise all window elements to nums[r]
        while ((long) nums[r] * (r - l + 1) - windowSum > k) {
            windowSum -= nums[l++];
        }
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}

// LC 159 - Longest Substring with At Most Two Distinct Characters
// IDEA: Sliding window with HashMap — shrink when distinct > 2
// time = O(N), space = O(1)
public int lengthOfLongestSubstringTwoDistinct(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    int l = 0, ans = 0;
    for (int r = 0; r < s.length(); r++) {
        freq.merge(s.charAt(r), 1, Integer::sum);
        while (freq.size() > 2) {
            char lc = s.charAt(l);
            freq.merge(lc, -1, Integer::sum);
            if (freq.get(lc) == 0) freq.remove(lc);
            l++;
        }
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}