Hash Map — Worked Examples

# Python - SortedDict (from sortedcontainers)
from sortedcontainers import SortedDict

# TreeMap Pattern Template
def treemap_pattern(data, target):
    # SortedDict keeps keys in sorted order
    tree_map = SortedDict()

    # Basic operations
    tree_map[key] = value           # O(log n) insert
    value = tree_map.get(key)       # O(1) !! backed by a hash dict, NOT a tree walk
    del tree_map[key]               # O(log n) delete

    # Ordered access — keys() is an INDEXABLE sorted view (O(log n) random access)
    keys = tree_map.keys()
    first_key = keys[0]  if tree_map else None          # firstKey()
    last_key  = keys[-1] if tree_map else None          # lastKey()
    tree_map.peekitem(0)                                # firstEntry() -> (k, v)
    tree_map.peekitem(-1)                               # lastEntry()  -> (k, v)

    # Floor / Ceiling — use the SortedDict's OWN bisect methods.
    # ❌ do NOT do `bisect.bisect_left(list(tree_map.keys()), target)`
    #    -> list(...) copies every key = O(n), killing the O(log n) win
    i = tree_map.bisect_left(target)    # first index with key >= target
    j = tree_map.bisect_right(target)   # first index with key >  target

    ceil_key  = keys[i]     if i < len(tree_map) else None   # ceilingKey(target)
    floor_key = keys[j - 1] if j > 0             else None   # floorKey(target)

    # Range query: all keys in [lo, hi]
    for k in tree_map.irange(lo, hi):                   # subMap(lo, true, hi, true)
        process(k, tree_map[k])

    return tree_map

# Examples: LC 853, LC 729/731/732, LC 846, LC 352, LC 981

# python — the safe floor/ceiling idiom
i = d.bisect_left(x)
ceil_key = d.keys()[i] if i < len(d) else None      # ceilingKey(x)

j = d.bisect_right(x) - 1
floor_key = d.keys()[j] if j >= 0 else None         # floorKey(x)

// Java - TreeMap Pattern
import java.util.*;

// TreeMap Pattern Template
public void treeMapPattern(int[] data) {
    // TreeMap maintains sorted order by key (Red-Black Tree)
    TreeMap<Integer, Integer> treeMap = new TreeMap<>();

    // Basic operations - O(log n)
    treeMap.put(key, value);        // Insert
    Integer value = treeMap.get(key);  // Search
    treeMap.remove(key);            // Delete

    // Ordered operations - O(log n)
    Integer firstKey = treeMap.firstKey();   // Min key
    Integer lastKey = treeMap.lastKey();     // Max key
    Integer floorKey = treeMap.floorKey(k);  // Largest key <= k
    Integer ceilKey = treeMap.ceilingKey(k); // Smallest key >= k

    // Lower/Higher (exclusive)
    Integer lower = treeMap.lowerKey(k);     // Largest key < k
    Integer higher = treeMap.higherKey(k);   // Smallest key > k

    // Range queries - O(k log n) where k is range size
    Map.Entry<Integer, Integer> firstEntry = treeMap.firstEntry();
    Map.Entry<Integer, Integer> lastEntry = treeMap.lastEntry();

    // Iterate in sorted order - O(n)
    for (Map.Entry<Integer, Integer> entry : treeMap.entrySet()) {
        int key = entry.getKey();
        int val = entry.getValue();
        // Process in sorted order
    }

    // SubMap views (range queries)
    SortedMap<Integer, Integer> subMap = treeMap.subMap(fromKey, toKey);
    SortedMap<Integer, Integer> headMap = treeMap.headMap(toKey);
    SortedMap<Integer, Integer> tailMap = treeMap.tailMap(fromKey);
}

# Python - LC 853 Car Fleet
def carFleet(target, position, speed):
    # Use sorted iteration (similar to TreeMap)
    cars = sorted(zip(position, speed), reverse=True)  # Sort by position descending

    stack = []
    for pos, spd in cars:
        time = (target - pos) / spd  # Time to reach target
        if not stack or time > stack[-1]:
            stack.append(time)

    return len(stack)

# Alternative using SortedDict
from sortedcontainers import SortedDict

def carFleet_v2(target, position, speed):
    car_map = SortedDict()
    for p, s in zip(position, speed):
        car_map[-p] = s  # Negative for reverse order

    fleets = 0
    prev_time = 0

    for neg_pos, spd in car_map.items():
        pos = -neg_pos
        time = (target - pos) / spd
        if time > prev_time:
            fleets += 1
            prev_time = time

    return fleets

// Java - LC 853 Car Fleet
/**
 * time = O(N log N)
 * space = O(N)
 */
public int carFleet(int target, int[] position, int[] speed) {
    // Build HashMap first
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < position.length; i++) {
        map.put(position[i], speed[i]);
    }

    // Convert to TreeMap for sorted iteration (descending order)
    TreeMap<Integer, Integer> treeMap = new TreeMap<>(Collections.reverseOrder());
    treeMap.putAll(map);

    int fleets = 0;
    double prevTime = 0;

    // Iterate from position closest to target (sorted order)
    for (Map.Entry<Integer, Integer> entry : treeMap.entrySet()) {
        int pos = entry.getKey();
        int spd = entry.getValue();
        double time = (double)(target - pos) / spd;

        // If current car takes longer, it forms a new fleet
        if (time > prevTime) {
            fleets++;
            prevTime = time;
        }
    }

    return fleets;
}

// Java - LC 729 My Calendar I
/**
 * time = O(log N) per operation
 * space = O(N)
 */
class MyCalendar {
    TreeMap<Integer, Integer> calendar;

    public MyCalendar() {
        calendar = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        // Find largest start time <= current start
        Integer prev = calendar.floorKey(start);

        // Find smallest start time >= current start
        Integer next = calendar.ceilingKey(start);

        // Check no overlap with previous booking
        if (prev != null && calendar.get(prev) > start) {
            return false;
        }

        // Check no overlap with next booking
        if (next != null && next < end) {
            return false;
        }

        calendar.put(start, end);
        return true;
    }
}

# python
# LC 729 - My Calendar I
# V1) Closest 1:1 translation of the Java floorKey / ceilingKey solution
from sortedcontainers import SortedDict

class MyCalendar:
    # time = O(log N) per booking, space = O(N)
    def __init__(self):
        self.calendar = SortedDict()   # start -> end

    def book(self, start: int, end: int) -> bool:
        keys = self.calendar.keys()

        # floorKey(start): largest key <= start
        i = self.calendar.bisect_right(start)
        prev = keys[i - 1] if i > 0 else None

        # ceilingKey(start): smallest key >= start
        j = self.calendar.bisect_left(start)
        nxt = keys[j] if j < len(keys) else None

        if (prev is None or self.calendar[prev] <= start) and \
           (nxt is None or end <= nxt):
            self.calendar[start] = end
            return True
        return False

# python
# LC 729 - My Calendar I
# V2) More idiomatic — SortedList of (start, end) tuples.
#     ONE structure, no key/value split; the overlap check reads directly.
#     This is the version to write in an interview.
from sortedcontainers import SortedList

class MyCalendar:
    # time = O(log N) per booking, space = O(N)
    def __init__(self):
        self.books = SortedList()      # sorted list of (start, end)

    def book(self, start: int, end: int) -> bool:
        i = self.books.bisect_left((start, end))
        if i > 0 and self.books[i - 1][1] > start:            # prev event overlaps
            return False
        if i < len(self.books) and end > self.books[i][0]:    # next event overlaps
            return False
        self.books.add((start, end))
        return True

# python
# LC 729 - My Calendar I
# V3) Zero-dependency fallback (stdlib only) — search stays O(log N),
#     but list.insert() shifts elements => O(N) per booking.
#     Fine for LC 729's constraints (<= 1000 calls).
import bisect

class MyCalendar:
    # time = O(N) per booking, space = O(N)
    def __init__(self):
        self.books = []                # sorted list of (start, end)

    def book(self, start: int, end: int) -> bool:
        i = bisect.bisect_left(self.books, (start, end))
        if i > 0 and self.books[i - 1][1] > start:
            return False
        if i < len(self.books) and end > self.books[i][0]:
            return False
        self.books.insert(i, (start, end))
        return True

# LC 347 Top K Frequent Elements — O(n) bucket approach
from collections import Counter

def topKFrequent(nums: list, k: int) -> list:
    count = Counter(nums)
    # bucket[i] = list of numbers that appear exactly i times
    bucket = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        bucket[freq].append(num)

    result = []
    for freq in range(len(bucket) - 1, 0, -1):
        result.extend(bucket[freq])
        if len(result) >= k:
            return result[:k]
    return result

# LC 692 Top K Frequent Words — bucket + sort within bucket
from collections import Counter

def topKFrequent_words(words: list, k: int) -> list:
    count = Counter(words)
    bucket = [[] for _ in range(len(words) + 1)]
    for word, freq in count.items():
        bucket[freq].append(word)

    result = []
    for freq in range(len(bucket) - 1, 0, -1):
        bucket[freq].sort()          # alphabetical within same frequency
        result.extend(bucket[freq])
        if len(result) >= k:
            return result[:k]
    return result

# LC 139 Word Break — {index: bool}
def wordBreak(s: str, wordDict: list) -> bool:
    word_set = set(wordDict)
    memo = {}

    def dp(i):
        if i == len(s):
            return True
        if i in memo:
            return memo[i]
        for j in range(i + 1, len(s) + 1):
            if s[i:j] in word_set and dp(j):
                memo[i] = True
                return True
        memo[i] = False
        return False

    return dp(0)

# LC 1048 Longest String Chain — {word: longest_chain_ending_here}
def longestStrChain(words: list) -> int:
    words.sort(key=len)
    dp = {}   # word -> longest chain ending at this word
    best = 1
    for word in words:
        dp[word] = 1
        for i in range(len(word)):
            prev = word[:i] + word[i+1:]   # remove one character
            if prev in dp:
                dp[word] = max(dp[word], dp[prev] + 1)
        best = max(best, dp[word])
    return best

# LC 322 Coin Change — classic DP, memo keyed by amount
def coinChange(coins: list, amount: int) -> int:
    memo = {}
    def dp(rem):
        if rem < 0: return float('inf')
        if rem == 0: return 0
        if rem in memo: return memo[rem]
        memo[rem] = min(dp(rem - c) + 1 for c in coins)
        return memo[rem]
    res = dp(amount)
    return res if res != float('inf') else -1

# LC 496 Next Greater Element I
# map each element of nums1 to its next-greater in nums2
def nextGreaterElement(nums1: list, nums2: list) -> list:
    next_greater = {}   # val -> next greater val in nums2
    stack = []          # monotonic decreasing stack

    for num in nums2:
        # pop all elements smaller than current — current is their next greater
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)

    return [next_greater.get(n, -1) for n in nums1]

# LC 503 Next Greater Element II (circular array)
def nextGreaterElements(nums: list) -> list:
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices

    for i in range(2 * n):   # traverse twice for circular
        while stack and nums[stack[-1]] < nums[i % n]:
            result[stack.pop()] = nums[i % n]
        if i < n:
            stack.append(i)
    return result

# LC 739 Daily Temperatures — index-based answer map
def dailyTemperatures(temps: list) -> list:
    result = [0] * len(temps)
    stack = []  # monotonic decreasing stack of indices

    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

# LC 187 Repeated DNA Sequences — find all length-10 substrings appearing ≥ 2 times
def findRepeatedDnaSequences(s: str) -> list:
    if len(s) <= 10:
        return []
    seen, repeated = set(), set()
    for i in range(len(s) - 9):
        sub = s[i:i+10]
        if sub in seen:
            repeated.add(sub)
        seen.add(sub)
    return list(repeated)

# General Rabin-Karp rolling hash template
def rabin_karp(s: str, pattern: str) -> list:
    """Return all start indices where pattern occurs in s."""
    n, m = len(s), len(pattern)
    if m > n:
        return []

    BASE = 26
    MOD = (1 << 61) - 1   # Mersenne prime — minimises collisions

    def char_val(c):
        return ord(c) - ord('a')

    # Precompute BASE^(m-1) mod MOD
    power = pow(BASE, m - 1, MOD)

    # Hash of pattern and first window
    p_hash = 0
    w_hash = 0
    for i in range(m):
        p_hash = (p_hash * BASE + char_val(pattern[i])) % MOD
        w_hash = (w_hash * BASE + char_val(s[i])) % MOD

    result = []
    for i in range(n - m + 1):
        if w_hash == p_hash and s[i:i+m] == pattern:  # verify on hash match
            result.append(i)
        if i < n - m:
            # Roll: remove leftmost, add new rightmost
            w_hash = (w_hash - char_val(s[i]) * power) % MOD
            w_hash = (w_hash * BASE + char_val(s[i + m])) % MOD

    return result

# LC 1044 Longest Duplicate Substring — binary search + rolling hash
def longestDupSubstring(s: str) -> str:
    BASE, MOD = 31, (1 << 61) - 1

    def has_dup(length):
        if length == 0:
            return ""
        power = pow(BASE, length - 1, MOD)
        h = 0
        for c in s[:length]:
            h = (h * BASE + ord(c) - ord('a')) % MOD
        seen = {h: 0}
        for i in range(1, len(s) - length + 1):
            h = (h - (ord(s[i-1]) - ord('a')) * power) % MOD
            h = (h * BASE + ord(s[i+length-1]) - ord('a')) % MOD
            if h in seen:
                # verify (collision guard)
                start = seen[h]
                if s[start:start+length] == s[i:i+length]:
                    return s[i:i+length]
            seen[h] = i
        return ""

    lo, hi, ans = 0, len(s) - 1, ""
    while lo <= hi:
        mid = (lo + hi) // 2
        dup = has_dup(mid)
        if dup:
            ans = dup
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

// java
// LC 336 - Palindrome Pairs
// IDEA: word -> index map; for each split point, probe for the reversed other half
// time = O(n * k^2), space = O(n * k)   (n words, k = max word length)
public List<List<Integer>> palindromePairs(String[] words) {
    Map<String, Integer> index = new HashMap<>();   // word -> its index
    for (int i = 0; i < words.length; i++) index.put(words[i], i);

    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < words.length; i++) {
        String w = words[i];
        for (int j = 0; j <= w.length(); j++) {
            String pref = w.substring(0, j), suf = w.substring(j);
            if (isPal(pref)) {                      // partner goes on the LEFT
                String back = new StringBuilder(suf).reverse().toString();
                Integer k = index.get(back);
                if (k != null && !back.equals(w)) res.add(Arrays.asList(k, i));
            }
            if (j != w.length() && isPal(suf)) {    // partner goes on the RIGHT
                String back = new StringBuilder(pref).reverse().toString();
                Integer k = index.get(back);
                if (k != null && !back.equals(w)) res.add(Arrays.asList(i, k));
            }
        }
    }
    return res;
}

private boolean isPal(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false;
    return true;
}

# python
# LC 336 - Palindrome Pairs
# IDEA: {word: index}; for each split point, probe for the reversed other half
# time = O(n * k^2), space = O(n * k)
def palindromePairs(words: list) -> list:
    index = {w: i for i, w in enumerate(words)}
    res = []
    for i, w in enumerate(words):
        n = len(w)
        for j in range(n + 1):
            pref, suf = w[:j], w[j:]
            if pref == pref[::-1]:                 # partner goes on the LEFT
                back = suf[::-1]
                if back in index and back != w:
                    res.append([index[back], i])
            if j != n and suf == suf[::-1]:        # partner goes on the RIGHT
                back = pref[::-1]
                if back in index and back != w:
                    res.append([i, index[back]])
    return res

tasks = AAABBB, n = 2   → maxFreq = 3, countOfMax = 2 (A and B)

  | A B idle | A B idle | A B
  \___ n+1 ___/\___ n+1 __/ \_countOfMax_/

  slots = (3-1)*(2+1) + 2 = 8

// java
// LC 621 - Task Scheduler
// IDEA: only the max frequency and how many tasks tie for it matter
// time = O(N), space = O(1)  (26 keys)
public int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    int maxFreq = 0;
    for (char t : tasks) maxFreq = Math.max(maxFreq, ++freq[t - 'A']);
    int countOfMax = 0;
    for (int f : freq) if (f == maxFreq) countOfMax++;
    int slots = (maxFreq - 1) * (n + 1) + countOfMax;
    return Math.max(tasks.length, slots);           // no idle time needed if tasks are diverse
}

// LC 767 - Reorganize String  (same max-frequency test, then even/odd fill)
// time = O(n), space = O(n)
public String reorganizeString(String s) {
    int[] cnt = new int[26];
    int maxFreq = 0, maxChar = 0;
    for (char c : s.toCharArray()) {
        cnt[c - 'a']++;
        if (cnt[c - 'a'] > maxFreq) { maxFreq = cnt[c - 'a']; maxChar = c - 'a'; }
    }
    int n = s.length();
    if (maxFreq > (n + 1) / 2) return "";           // impossible

    char[] res = new char[n];
    int i = 0;
    while (cnt[maxChar] > 0) {                      // most frequent char at even slots first
        res[i] = (char) ('a' + maxChar); i += 2; cnt[maxChar]--;
    }
    for (int c = 0; c < 26; c++) {
        while (cnt[c] > 0) {
            if (i >= n) i = 1;                      // wrap to odd slots
            res[i] = (char) ('a' + c); i += 2; cnt[c]--;
        }
    }
    return new String(res);
}

# python
# LC 621 - Task Scheduler
# IDEA: (maxFreq - 1) frames of width (n + 1), plus every task tied for maxFreq
# time = O(N), space = O(1)  (26 keys)
from collections import Counter

def leastInterval(tasks: list, n: int) -> int:
    freq = Counter(tasks)
    max_freq = max(freq.values())
    count_of_max = sum(1 for f in freq.values() if f == max_freq)
    return max(len(tasks), (max_freq - 1) * (n + 1) + count_of_max)

# python
# LC 767 - Reorganize String
# IDEA: feasible iff max_freq <= (n+1)//2; fill slots 0,2,4,... then 1,3,5,... in freq order
# time = O(n log 26) ~ O(n), space = O(n)
def reorganizeString(s: str) -> str:
    freq = Counter(s)
    if max(freq.values()) > (len(s) + 1) // 2:
        return ""
    res = [''] * len(s)
    i = 0
    for ch, cnt in freq.most_common():          # most frequent first — this is what makes it work
        for _ in range(cnt):
            if i >= len(s):
                i = 1                           # even slots exhausted → switch to odd slots
            res[i] = ch
            i += 2
    return "".join(res)

Transform the binary array:
- Treat 0 as -1
- Treat 1 as +1

Why? Equal 0s and 1s → sum of transformed array = 0

Map<Integer, Integer> map = new HashMap<>();
// {count: first_index_where_count_occurred}

map.put(0, -1); // Initialize for subarrays starting at index 0

count: running sum (cumulative)
  - +1 for each 1
  - -1 for each 0

If count(i) == count(j) where i < j:
  → Elements between i and j sum to 0
  → Subarray [i+1, j] is balanced (equal 0s and 1s)
  → Length = j - i

To maximize length, we want the earliest index with this count.
If count appears at indices [3, 7, 10]:
  - Store index 3
  - When we see count again at index 10, length = 10 - 3 = 7 (maximum)

If from index 0 to i, count = 0:
  → Entire subarray [0, i] is balanced
  → Length = i - (-1) = i + 1 ✓

Without this initialization, we'd miss subarrays starting at index 0.

Let count(i) = cumulative sum at index i

If count(i) == count(j) where i < j:
  count(j) - count(i) = 0

This means:
  sum of elements from index (i+1) to j = 0

In transformed array (0→-1, 1→+1):
  sum = 0 means equal number of -1s and +1s
  → equal number of 0s and 1s in original array

// Java Template
public int findMaxLength(int[] nums) {
    // Map: {count: first_index_where_count_occurred}
    Map<Integer, Integer> map = new HashMap<>();

    // Initialize: handle subarrays starting at index 0
    map.put(0, -1);

    int maxLen = 0;
    int count = 0;

    for (int i = 0; i < nums.length; i++) {
        // Transform: 0 → -1, 1 → +1
        count += (nums[i] == 1) ? 1 : -1;

        // If count seen before: calculate subarray length
        if (map.containsKey(count)) {
            maxLen = Math.max(maxLen, i - map.get(count));
        } else {
            // Store FIRST occurrence only (for max length)
            map.put(count, i);
        }
    }

    return maxLen;
}

# Python Template
def findMaxLength(nums):
    # Map: {count: first_index_where_count_occurred}
    d = {0: -1}  # Initialize for subarrays starting at index 0

    max_len = 0
    count = 0

    for i, num in enumerate(nums):
        # Transform: 0 → -1, 1 → +1
        count += 1 if num == 1 else -1

        # If count seen before: calculate subarray length
        if count in d:
            max_len = max(max_len, i - d[count])
        else:
            # Store FIRST occurrence only (for max length)
            d[count] = i

    return max_len

If prefix[i] % k == prefix[j] % k  (where j < i)

Then:
  (prefix[i] - prefix[j]) % k == 0

Which means:
  prefix[i] - prefix[j] = sum of nums[j+1 .. i]

Therefore:
  The subarray [j+1, i] has a sum divisible by k

Map<Integer, Integer> map = new HashMap<>();
// {remainder: count}  ← Store COUNT, not index (similar to LC 560)

map.put(0, 1); // Initialize for subarrays starting from beginning

This is a "count ALL subarrays" problem (like LC 560).

If remainder 3 appears at indices [2, 5, 8]:
  - When we reach index 5: add 1 (subarray from index 2 to 5)
  - When we reach index 8: add 2 (subarrays from 2→8 and 5→8)

Total: 3 valid subarrays

int remainder = prefixSum % k;

// MUST adjust negative remainders to positive
if (remainder < 0) {
    remainder += k;
}

// Or use this one-liner:
remainder = ((prefixSum % k) + k) % k;

If prefixSum % k == 0 at some index i:
  → The entire subarray [0, i] is divisible by k
  → We need to count this case

Without initialization, we'd miss these subarrays.

// Java Template
public int subarraysDivByK(int[] nums, int k) {
    // Map: {remainder: count}
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1); // Handle subarrays from beginning

    int count = 0;
    int prefixSum = 0;

    for (int num : nums) {
        prefixSum += num;

        // Calculate remainder (handle negatives!)
        int remainder = prefixSum % k;
        if (remainder < 0) {
            remainder += k;
        }
        // Or: int remainder = ((prefixSum % k) + k) % k;

        // Add count of all previous same remainders
        count += map.getOrDefault(remainder, 0);

        // Update remainder count
        map.put(remainder, map.getOrDefault(remainder, 0) + 1);
    }

    return count;
}

# Python Template
def subarraysDivByK(nums, k):
    # Map: {remainder: count}
    remainder_count = {0: 1}

    count = 0
    prefix_sum = 0

    for num in nums:
        prefix_sum += num

        # Calculate remainder (Python % handles negatives correctly)
        remainder = prefix_sum % k

        # Add count of all previous same remainders
        count += remainder_count.get(remainder, 0)

        # Update remainder count
        remainder_count[remainder] = remainder_count.get(remainder, 0) + 1

    return count

public int subarraysDivByK(int[] nums, int k) {
    int[] remainderCount = new int[k];
    remainderCount[0] = 1;

    int count = 0;
    int prefixSum = 0;

    for (int num : nums) {
        prefixSum += num;
        int remainder = ((prefixSum % k) + k) % k;

        count += remainderCount[remainder];
        remainderCount[remainder]++;
    }

    return count;
}

prefixSum = -1: remainder = -1 (wrong!)
prefixSum = -3: remainder = -3 (wrong!)
prefixSum = -6: remainder = -1 (wrong!)

prefixSum = -1: remainder = 4 (correct: -1 ≡ 4 mod 5)
prefixSum = -3: remainder = 2 (correct: -3 ≡ 2 mod 5)
prefixSum = -6: remainder = 4 (correct: -6 ≡ 4 mod 5)

map: {oddCount: frequency}
     → "How many times has this odd-count appeared so far?"

At index i with current oddCount:
  → Find how many previous positions had exactly (oddCount - k) odds
  → Those form subarrays with exactly k odds ending at i

If oddCount == k at index i:
  → Entire subarray [0, i] has exactly k odds
  → oddCount - k = 0, must have {0: 1} pre-initialized

// Java - LC 1248
public int numberOfSubarrays(int[] nums, int k) {
    // map: {oddCount: frequency}
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);  // base case: 0 odds seen 1 time

    int res = 0, oddCount = 0;

    for (int num : nums) {
        if (num % 2 == 1) oddCount++;  // treat odd as +1

        // How many previous positions had (oddCount - k) odds?
        res += map.getOrDefault(oddCount - k, 0);

        // Update count AFTER checking (critical order!)
        map.put(oddCount, map.getOrDefault(oddCount, 0) + 1);
    }

    return res;
}

# python - LC 1248
# IDEA: prefix ODD-count + hashmap (same shape as LC 560)
# time: O(n), space: O(n)
# ref: leetcode_python/Array/count-number-of-nice-subarrays.py
class Solution:
    def numberOfSubarrays(self, nums, k):
        total_cnt = 0
        prefix_cnt = 0                 # running count of odd numbers so far

        cnt_map = {0: 1}              # {odd_count : frequency}; base case 0 odds seen once

        for val in nums:
            if val % 2 == 1:          # treat odd as +1 (even contributes 0)
                prefix_cnt += 1

            # NOTE: += get(prefix_cnt - k), NOT += 1
            #   there may be MULTIPLE earlier prefixes with the same odd count,
            #   each one gives a distinct valid subarray ending here
            total_cnt += cnt_map.get(prefix_cnt - k, 0)

            # record current prefix count AFTER checking (avoid self-count)
            cnt_map[prefix_cnt] = cnt_map.get(prefix_cnt, 0) + 1

        return total_cnt

// Exactly k = atMost(k) - atMost(k-1)
public int numberOfSubarrays(int[] nums, int k) {
    return atMost(nums, k) - atMost(nums, k - 1);
}

private int atMost(int[] nums, int k) {
    int l = 0, res = 0, oddCount = 0;
    for (int r = 0; r < nums.length; r++) {
        if (nums[r] % 2 == 1) oddCount++;
        while (oddCount > k) {
            if (nums[l] % 2 == 1) oddCount--;
            l++;
        }
        res += (r - l + 1);
    }
    return res;
}

# 523 Continuous Subarray Sum
# IDEA : HASH TABLE
# -> if sum(nums[i:j]) % k == 0 for some i < j, 
#   ->  then sum(nums[:j]) % k == sum(nums[:i]) % k  !!!!
#   -> So we just need to use a dict to keep track of sum(nums[:i]) % k 
#   -> and the corresponding index i. Once some later sum(nums[:i']) % k == sum(nums[:i]) % k and i' - i > 1, so we return True.
class Solution(object):
    def checkSubarraySum(self, nums, k):
        """
        # _dict = {0:-1} : for edge case (need to find a continuous subarray of size AT LEAST two )
        # https://leetcode.com/problems/continuous-subarray-sum/discuss/236976/Python-solution
        # 0: -1 is for edge case that current sum mod k == 0
        # demo :
                In [93]: nums = [0]
                    ...: k = 1
                    ...:
                    ...:
                    ...: s = Solution()
                    ...: r = s.checkSubarraySum(nums, k)
                    ...: print (r)
                0
                i - _dict[tmp] = 1
                False
        """
        ### NOTE : we need to init _dict as {0:-1}
        _dict = {0:-1}
        tmp = 0
        for i in range(len(nums)):
            tmp += nums[i]
            if k != 0:
                ### NOTE : we get remainder of tmp by k
                tmp = tmp % k
            # if tmp in _dict, means there is the other sub part make sub array sum % k == 0
            if tmp in _dict:
                ### only if continuous sub array with length >= 2
                if i - _dict[tmp] > 1:
                    return True
            else:
                _dict[tmp] = i
        return False

# LC 003
# IDEA : TWO POINTER + SLIDING WINDOW + DICT (NOTE this method !!!!)
#       -> 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
        """
        NOTE !!!

        we move right pointer first, then left pointer
        """
        # NOTE !!! right pointer
        for r in range(len(s)):
            """
            ### NOTE : deal with "s[r] in d" case ONLY !!! 
            ### 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

# LC 204 Count Primes
# IDEA : dict
# https://leetcode.com/problems/count-primes/discuss/1343795/python%3A-sieve-of-eretosthenes
# prime(x) : check if x is a prime
# prime(0) = 0
# prime(1) = 0
# prime(2) = 0
# prime(3) = 1
# prime(4) = 2
# prime(5) = 3
# python 3
class Solution:
    def countPrimes(self, n):
        # using sieve of eretosthenes algorithm
        if n < 2: return 0
        nonprimes = set()
        for i in range(2, round(n**(1/2))+1):
            if i not in nonprimes:
                for j in range(i*i, n, i):
                    nonprimes.add(j)
        return n - len(nonprimes) - 2  # remove prime(1), prime(2)

# python
# LC 036 Valid Sudoku
class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        n = len(board)
        return self.isValidRow(board) and self.isValidCol(board) and self.isValidNineCell(board)
        
    def isValidRow(self, board):
        n = len(board)
        for r in range(n):
            row = [x for x in board[r] if x != '.']
            if len(set(row)) != len(row): # if not repetition 
                return False
        return True

    def isValidCol(self, board):
        n = len(board)
        for c in range(n):
            col = [board[r][c] for r in range(n) if board[r][c] != '.']
            if len(set(col)) != len(col): # if not repetition 
                return False
        return True

    def isValidNineCell(self, board):
        n = len(board)
        for r in range(0, n, 3):
            for c in range(0, n, 3):
                cell = []
                for i in range(3):
                    for j in range(3):
                        num = board[r + i][c + j]
                        if num != '.':
                            cell.append(num)
                if len(set(cell)) != len(cell): # if not repetition 
                    return False
        return True

// java
// LC 36 Valid Sudoku
// IDEA: one pass, three sets per index -- row, column and 3x3 box.
//       The box index is (r/3)*3 + c/3, which is the whole trick.
// time = O(81) = O(1), space = O(81) = O(1)
public boolean isValidSudoku(char[][] board) {
    Set<Character>[] rows = new HashSet[9];
    Set<Character>[] cols = new HashSet[9];
    Set<Character>[] boxes = new HashSet[9];
    for (int i = 0; i < 9; i++) {
        rows[i] = new HashSet<>();
        cols[i] = new HashSet<>();
        boxes[i] = new HashSet<>();
    }

    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            char v = board[r][c];
            if (v == '.') continue;

            /** NOTE !!! the box a cell belongs to */
            int b = (r / 3) * 3 + c / 3;

            // Set.add returns false when the value was already there -> duplicate
            if (!rows[r].add(v) || !cols[c].add(v) || !boxes[b].add(v)) {
                return false;
            }
        }
    }
    return true;
}

# LC 1010. Pairs of Songs With Total Durations Divisible by 60
# IDEA : dict
# IDEA : NOTE : we only count "NUMBER OF PAIRS", instead get all pairs indexes
class Solution(object):
    def numPairsDivisibleBy60(self, time):
        rem = {}
        pairs = 0
        for t in time:
            #print ("rem = " + str(rem))
            t %= 60
            if (60 - t) % 60 in rem:
                """
                NOTE : this trick
                -> we append "all 60 duration combinations count" via the existing times of element "(60 - t) % 60" 
                """
                pairs += rem[(60 - t) % 60]
            if t not in rem:
                rem[t] = 1
            else:
                ### NOTE : here : we plus 1 when an element already exist
                rem[t] += 1
        return pairs

# LC 560 : Subarray Sum Equals K

# IDEA : HASH TABLE + sub array sum
# IDEA : https://blog.csdn.net/fuxuemingzhu/article/details/82767119
class Solution(object):
    def subarraySum(self, nums, k):
        n = len(nums)
        d = collections.defaultdict(int)
        d[0] = 1
        sum = 0
        res = 0
        for i in range(n):
            sum += nums[i]
            # if sum - k in d
            #  -> if sum - (every _ in d) == k
            if sum - k in d:
                res += d[sum - k]
            d[sum] += 1
        return res

// LC 560 : Subarray Sum Equals K
// java
// (algorithm book (labu) p.350)
// V1 : brute force + cum sum
int subarraySum(int[] nums, int k){
    int n = nums.length;
    // init pre sum
    int[] sum = new int[n+1];
    sum[0] = 0;
    for (int i = 0; i < n; i++){
        sum[i+1] = sum[i] + nums[i];
    }

    int ans = 0;
    // loop over all sub array
    for (int i=1; i <= n; i++){
        for (int j=0; j < i; j++){
            // sum of nums[j...i-1]
            if (sum[i] - sum[j] == k){
                ans += 1;
            }
        }
    }
    return ans;
}

// (algorithm book (labu) p.350)
// V2 : hash map + cum sum
int subarraySum(int[] nums, int k){
    int n = nums.length;
    // map :  key : prefix, value : prefix exists count
    // init hash map
    HashMap<Integer, Integer> preSum = new HashMap<Integer, Integer>();

    // base case
    preSum.put(0,1);

    int ans = 0;
    int sum0_i = 0;

    for (int i = 0; i < n; i++){
        sum0_i += nums[i];
        // for presum : nums[0..j]
        int sum0_j = sum0_i - k;
        // if there is already presum, update the ans directly
        if (preSum.containsKey(sum0_j)){
            ans += preSum.get(sum0_j);
        }
        // add prefix and nums[0..i] and record exists count
        preSum.put(sum0_i, preSum.getOrDefault(sum0_i,0) + 1);
    }
    return ans;
}

# LC 532 K-diff Pairs in an Array
# V0
# IDEA : HASH TABLE
import collections
class Solution(object):
    def findPairs(self, nums, k):
        answer = 0
        cnt = collections.Counter(nums)
        # NOTE THIS : !!! we use set(nums) for reduced time complexity, and deal with k == 0 case separately
        for num in set(nums):
            """
            # [b - a] = k
            #  -> b - a = +k or -k
            #  -> b = k + a or b = -k + a
            #  -> however, 0 <= k <= 10^7, so ONLY b = k + a is possible

            2 cases
                -> case 1) k > 0 and num + k in cnt
                -> case 2) k == 0 and cnt[num] > 1
            """
            # case 1) k > 0 and num + k in cnt
            if k > 0 and num + k in cnt: # | a - b | = k -> a - b = +k or -k, but here don't have to deal with "a - b = -k" case, since this sutuation will be covered when go through whole nums  
                answer += 1
            # case 2) k == 0 and cnt[num] > 1
            if k == 0 and cnt[num] > 1:  # for cases k = 0 ->  pair like (1,1) will work. (i.e. 1 + (-1))
                answer += 1
        return answer

# V0'
# IDEA : SORT + BRUTE FORCE + BREAK
class Solution(object):
    def findPairs(self, nums, k):
        # edge case
        if not nums and k:
            return 0
        nums.sort()
        res = 0
        tmp = []
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if abs(nums[j] - nums[i]) == k:
                    cur = [nums[i], nums[j]]
                    cur.sort()
                    if cur not in tmp:
                        res += 1
                        tmp.append(cur)
                elif abs(nums[j] - nums[i]) > k:
                    break
        return res

# LC 734. Sentence Similarity
# V0'
# https://zxi.mytechroad.com/blog/hashtable/leetcode-734-sentence-similarity/
import collections
class Solution(object):
    def areSentencesSimilar(self, words1, words2, pairs):
        if len(words1) != len(words2): return False
        similars = collections.defaultdict(set)
        for w1, w2 in pairs:
            similars[w1].add(w2)
            similars[w2].add(w1)
        for w1, w2 in zip(words1, words2):
            if w1 != w2 and w2 not in similars[w1]:
                return False
        return True

# V0
# IDEA : array op
#   -> Apart from edge cases
#   -> there are cases we need to consider
#     -> 1) if sentence1[i] == sentence2[i]
#     -> 2) if sentence1[i] != sentence2[i] and
#           -> [sentence1[i], sentence2[i]] in similarPairs
#           -> [sentence2[i], sentence1[i]] in similarPairs
class Solution(object):
    def areSentencesSimilar(self, sentence1, sentence2, similarPairs):
        # edge case
        if sentence1 == sentence2:
            return True
        if len(sentence1) != len(sentence2):
            return False
        for i in range(len(sentence1)):
            tmp = [sentence1[i], sentence2[i]]
            """
            NOTE : below condition
                1) sentence1[i] != sentence2[i]
                  AND
                2) (tmp not in similarPairs and tmp[::-1] not in similarPairs)

                -> return false
            """
            if sentence1[i] != sentence2[i] and (tmp not in similarPairs and tmp[::-1] not in similarPairs):
                return False
        return True

# LC 146 LRU Cache
# note : there is also array/queue approach
# IDEA : Ordered dictionary
# https://leetcode.com/problems/lru-cache/solution/
# IDEA : 
#       -> There is a structure called ordered dictionary, it combines behind both hashmap and linked list. 
#       -> In Python this structure is called OrderedDict 
#       -> and in Java LinkedHashMap.
from collections import OrderedDict
class LRUCache(OrderedDict):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self:
            return - 1
        
        self.move_to_end(key)
        return self[key]

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last = False)

# LC 438. Find All Anagrams in a String
# IDEA : SLIDING WINDOW + collections.Counter()
class Solution(object):
    def findAnagrams(self, s, p):
        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 554. Brick Wall
# IDEA : HASH TABLE + COUNTER UPDATE (looping every element in the list and cumsum and 
import collections
class Solution(object):
    def leastBricks(self, wall):
        _counter = collections.Counter()
        count = 0
        # go through every sub-wall in wall
        for w in wall:
            cum_sum = 0
            # go through every element in sub-wall
            for i in range(len(w) - 1):
                cum_sum += w[i]
                ### NOTE we can update collections.Counter() via below
                _counter.update([cum_sum])
                count = max(count, _counter[cum_sum])
        return len(wall) - count

// LC 325 — prefix sum + hashmap, store FIRST occurrence (max length variant)
// Key: prefixSum[j] - prefixSum[i] = k  →  check if (curSum - k) exists in map
public int maxSubArrayLen(int[] nums, int k) {
    Map<Integer, Integer> preSumMap = new HashMap<>();
    preSumMap.put(0, -1); // handle subarrays starting at index 0

    int curSum = 0, maxSize = 0;
    for (int i = 0; i < nums.length; i++) {
        curSum += nums[i];
        if (preSumMap.containsKey(curSum - k)) {
            maxSize = Math.max(maxSize, i - preSumMap.get(curSum - k));
        }
        preSumMap.putIfAbsent(curSum, i); // store FIRST occurrence only
    }
    return maxSize;
}

// java
// LC 1257

// IDEA: HASHMAP (fixed by gpt)
// TODO: validate
public String findSmallestRegion_0_1(List<List<String>> regions, String region1, String region2) {

    // Map each region to its parent
    /**
     *  NOTE !!!
     *
     *   map : {child : parent}
     *
     *   -> so the key is child, and the value is its parent
     *
     */
    Map<String, String> parentMap = new HashMap<>();

    for (List<String> regionList : regions) {
        String parent = regionList.get(0);
        for (int i = 1; i < regionList.size(); i++) {
            parentMap.put(regionList.get(i), parent);
        }
    }

    // Track ancestors of region1
    /**  NOTE !!!
     *
     *  we use `set` to track `parents` (ancestors)
     *  if exists, add it to set,
     *  and set `current region` as its `parent`
     *
     */
    Set<String> ancestors = new HashSet<>();
    while (region1 != null) {
        ancestors.add(region1);
        region1 = parentMap.get(region1);
    }

    // Traverse region2’s ancestors until we find one in region1’s ancestor set
    while (!ancestors.contains(region2)) {
        region2 = parentMap.get(region2);
    }

    return region2;
}

Step 1: Build productCount map
  for i in [0, n):
    for j in (i, n):
      productCount[nums[i]*nums[j]]++

Step 2: For each count n >= 2:
  ans += C(n, 2) * 8
       = n*(n-1)/2 * 8
       = 4 * n * (n-1)

// LC 1726 - Tuple with Same Product
// Time: O(N^2)  Space: O(N^2)
public int tupleSameProduct(int[] nums) {
    Map<Integer, Integer> productCount = new HashMap<>();

    // Step 1: count frequency of each pair product
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            int product = nums[i] * nums[j];
            productCount.put(product, productCount.getOrDefault(product, 0) + 1);
        }
    }

    // Step 2: for each product with n pairs, C(n,2) * 8 tuples
    int ans = 0;
    for (int count : productCount.values()) {
        if (count >= 2) {
            ans += count * (count - 1) / 2 * 8;
            // equivalent: ans += 4 * count * (count - 1);
        }
    }
    return ans;
}

C(n,2) * 8
= n*(n-1)/2 * 8
= 4 * n * (n-1)

pos = {value: current_index}   # O(1) lookup of "where is value v right now?"

For each index i (left → right):
  correct_val = sorted_arr[i]            # what SHOULD be at index i
  if arr[i] != correct_val:
     swap_idx = pos[correct_val]         # where correct_val currently is
     # 1) UPDATE the map BEFORE swapping (critical!)
     pos[arr[i]]      = swap_idx         # the value we move away keeps its new home
     pos[correct_val] = i                # correct_val is now at i
     # 2) swap in the array
     arr[i], arr[swap_idx] = arr[swap_idx], arr[i]
     swaps += 1

# python - LC 2471
from collections import deque

class Solution(object):
    def minimumOperations(self, root):
        # time  = O(N log M)  (M = widest level; sorting dominates per level)
        # space = O(M)
        q = deque([root])
        ops = 0

        while q:
            size = len(q)
            level = []
            for _ in range(size):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

            ops += self.min_swaps(level)   # add this level's cost

        return ops

    def min_swaps(self, arr):
        # min swaps to sort `arr` via {value: index} hashmap
        n = len(arr)
        sorted_arr = sorted(arr)
        pos = {v: i for i, v in enumerate(arr)}   # {value: current index}
        swaps = 0

        for i in range(n):
            correct_val = sorted_arr[i]
            if arr[i] != correct_val:
                swap_idx = pos[correct_val]

                # update map BEFORE swapping (so we don't lose arr[i]'s key)
                pos[arr[i]] = swap_idx
                pos[correct_val] = i

                # swap
                arr[i], arr[swap_idx] = arr[swap_idx], arr[i]
                swaps += 1

        return swaps

// java - LC 2471
/**
 * time  = O(N log M)   // M = widest level; sorting dominates
 * space = O(M)
 */
public int minimumOperations(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int ops = 0;

    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left != null)  q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        ops += minSwaps(level);
    }
    return ops;
}

// min swaps to sort via {value: index} map
private int minSwaps(List<Integer> arr) {
    int n = arr.size();
    Integer[] sorted = arr.toArray(new Integer[0]);
    Arrays.sort(sorted);

    Map<Integer, Integer> pos = new HashMap<>();   // {value: current index}
    for (int i = 0; i < n; i++) pos.put(arr.get(i), i);

    int swaps = 0;
    for (int i = 0; i < n; i++) {
        int correctVal = sorted[i];
        if (!arr.get(i).equals(correctVal)) {
            int swapIdx = pos.get(correctVal);

            // update map BEFORE swapping
            pos.put(arr.get(i), swapIdx);
            pos.put(correctVal, i);

            // swap
            int tmp = arr.get(i);
            arr.set(i, arr.get(swapIdx));
            arr.set(swapIdx, tmp);
            swaps++;
        }
    }
    return swaps;
}

sorted = [1, 2, 3]
pos    = {3:0, 1:1, 2:2}

i=0: correct=1, arr[0]=3 (mismatch)
     swap_idx = pos[1] = 1
     update map: pos[3]=1, pos[1]=0  → pos = {3:1, 1:0, 2:2}
     swap arr[0],arr[1] → arr = [1, 3, 2]   swaps=1

i=1: correct=2, arr[1]=3 (mismatch)
     swap_idx = pos[2] = 2
     update map: pos[3]=2, pos[2]=1  → pos = {3:2, 1:0, 2:1}
     swap arr[1],arr[2] → arr = [1, 2, 3]   swaps=2

i=2: correct=3, arr[2]=3 (match) → skip

Result: 2 swaps

Why LAST occurrence of the larger digit?
  - Moving a big digit further LEFT raises the most significant place → biggest gain.
  - Among equal large digits, taking the RIGHTMOST one leaves larger digits to the
    left untouched, keeping the tail as large as possible.

Why the FIRST improvable position (and stop)?
  - The leftmost place we can increase dominates all lower places → one swap there
    beats any swap further right. Only one swap is allowed, so return immediately.

digits = [2, 7, 3, 6]

Step 1 — build {digit: last index}:
  {2:0, 7:1, 3:2, 6:3}

Step 2 — scan left→right, for each digit look for a larger digit later:
  i=0, cur=2: check d=9..3 → d=7 exists at last[7]=1 > 0  ✓
              swap digits[0] and digits[1] → [7, 2, 3, 6]
              return 7236   (stop — only one swap allowed)

Result: 7236

# python
# LC 670 - Maximum Swap
# IDEA: {digit: last index} hashmap + greedy left scan
# time = O(n)  (n = number of digits), space = O(1)  (<= 10 keys)
class Solution(object):
    def maximumSwap(self, num):
        digits = list(str(num))

        # last occurrence index of each digit
        last = {int(d): i for i, d in enumerate(digits)}

        for i in range(len(digits)):
            cur = int(digits[i])
            # try the biggest digit (9..cur+1) that appears LATER
            for d in range(9, cur, -1):
                if last.get(d, -1) > i:
                    j = last[d]
                    digits[i], digits[j] = digits[j], digits[i]
                    return int("".join(digits))   # only ONE swap → stop

        return num   # already maximal

// java
// LC 670 - Maximum Swap
// time = O(n), space = O(1)  (<= 10 keys)
public int maximumSwap(int num) {
    char[] digits = String.valueOf(num).toCharArray();

    // last occurrence index of each digit 0-9
    int[] last = new int[10];
    for (int i = 0; i < digits.length; i++) {
        last[digits[i] - '0'] = i;
    }

    for (int i = 0; i < digits.length; i++) {
        int cur = digits[i] - '0';
        // try the biggest digit (9..cur+1) that appears LATER
        for (int d = 9; d > cur; d--) {
            if (last[d] > i) {
                // swap and return (only one swap allowed)
                char tmp = digits[i];
                digits[i] = digits[last[d]];
                digits[last[d]] = tmp;
                return Integer.parseInt(new String(digits));
            }
        }
    }
    return num; // already maximal
}

# python — 3-pointer variant
def maximumSwap(num):
    digits = list(str(num))
    left = right = 0
    max_idx = len(digits) - 1
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] > digits[max_idx]:
            max_idx = i                 # new largest digit to the right
        elif digits[i] < digits[max_idx]:
            left, right = i, max_idx    # candidate swap (keep the leftmost such i)
    digits[left], digits[right] = digits[right], digits[left]
    return int("".join(digits))

replacements_needed = window_size - (count of the most frequent char)
                    = (r - l + 1) - max_freq

# Python — Sliding Window + max_freq  (from leetcode_python/Hash_table/longest-repeating-character-replacement.py)
# time = O(n), space = O(1)  (only 26 uppercase letters)
class Solution:
    def characterReplacement(self, s, k):
        cnt_map = {}       # {char: count in current window}
        l = 0
        max_freq = 0       # highest single-char freq seen in the window
        max_len = 0

        for r in range(len(s)):
            # 1. update hash map FIRST
            cnt_map[s[r]] = cnt_map.get(s[r], 0) + 1

            # 2. track max frequency
            max_freq = max(max_freq, cnt_map[s[r]])

            # 3. shrink while replacements needed exceed k
            #    (no need to update max_freq here — removing s[l] can't raise it)
            while (r - l + 1) - max_freq > k:
                cnt_map[s[l]] -= 1
                l += 1

            # 4. record best valid window
            max_len = max(max_len, r - l + 1)

        return max_len

// Java — Sliding Window + maxFreq
// time = O(n), space = O(1)  (26 letters)
public int characterReplacement(String s, int k) {
    int[] cnt = new int[26];
    int l = 0, maxFreq = 0, maxLen = 0;

    for (int r = 0; r < s.length(); r++) {
        cnt[s.charAt(r) - 'A']++;
        maxFreq = Math.max(maxFreq, cnt[s.charAt(r) - 'A']);

        // shrink window when too many replacements needed
        while ((r - l + 1) - maxFreq > k) {
            cnt[s.charAt(l) - 'A']--;
            l++;
        }
        maxLen = Math.max(maxLen, r - l + 1);
    }
    return maxLen;
}

Time  = O(n)   -> r moves n times; l only moves forward (at most n times total)
Space = O(1)   -> hash map holds at most 26 uppercase letters

r advances 0 -> n-1 exactly once.
l NEVER moves backward; across the whole run it advances at most n times.
Total work = O(n + n) = O(n).

# LC 763 Partition Labels
# IDEA : GREEDY
class Solution(object):
    def partitionLabels(self, S):
        # note : this trick for get max index for each element in S
        lindex = { c: i for i, c in enumerate(S) }
        j = anchor = 0
        ans = []
        for i, c in enumerate(S):
            ### NOTE : trick here
            #          -> via below line of code, we can get the max idx of current substring which "has element only exist in itself"
            #          -> e.g. the index we need to do partition 
            j = max(j, lindex[c])
            print ("i = " + str(i) + "," + " c = " + str(c) + "," +   " j = " + str(j) + "," +  " ans = " + str(ans))
            if i == j:
                ans.append(j - anchor + 1)
                anchor = j + 1
        return ans