Advanced Hash Table (Min Window Substring · Randomized Set)

Minimum Window Substring (LeetCode 76)

Find the shortest substring in s that contains all characters in t.
Technique: Sliding Window + Hash Map.

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 left = 0, right = 0;
    int validCount = 0; // Number of characters that satisfy the required frequency
    int start = 0, minLen = Integer.MAX_VALUE;

    while (right < s.length()) {
        char c = s.charAt(right++);
        if (need.containsKey(c)) {
            window.merge(c, 1, Integer::sum);
            if (window.get(c).equals(need.get(c))) {
                validCount++;
            }
        }

        // Window satisfies t; try shrinking from the left
        while (validCount == need.size()) {
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }
            char d = s.charAt(left++);
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    validCount--;
                }
                window.merge(d, -1, Integer::sum);
            }
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

Find All Anagrams in a String (LeetCode 438)

Sliding window with frequency matching:

List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (s.length() < p.length()) return result;
    
    int[] pCount = new int[26], wCount = new int[26];
    for (char c : p.toCharArray()) pCount[c - 'a']++;

    int left = 0;
    for (int right = 0; right < s.length(); right++) {
        wCount[s.charAt(right) - 'a']++;
        
        // Maintain a window of size p.length()
        if (right - left + 1 == p.length()) {
            if (Arrays.equals(wCount, pCount)) {
                result.add(left);
            }
            wCount[s.charAt(left++) - 'a']--;
        }
    }
    return result;
}

Insert Delete GetRandom O(1) (LeetCode 380)

Combining a Hash Map (for O(1) lookup) and a Dynamic Array (for O(1) random access):

class RandomizedSet {
    private final Map<Integer, Integer> valToIndex = new HashMap<>(); 
    private final List<Integer> valList = new ArrayList<>();
    private final Random rand = new Random();

    public boolean insert(int val) {
        if (valToIndex.containsKey(val)) return false;
        valList.add(val);
        valToIndex.put(val, valList.size() - 1);
        return true;
    }

    public boolean remove(int val) {
        if (!valToIndex.containsKey(val)) return false;
        
        int idx = valToIndex.get(val);
        int lastVal = valList.get(valList.size() - 1);
        
        // Move the last element to the removal position to avoid shifting
        valList.set(idx, lastVal);
        valToIndex.put(lastVal, idx);
        
        // Remove the last element
        valList.remove(valList.size() - 1);
        valToIndex.remove(val);
        return true;
    }

    public int getRandom() {
        return valList.get(rand.nextInt(valList.size()));
    }
}

Key Optimization: When removing an element from the middle of an array, swap it with the last element. This avoids the O(n) overhead of shifting elements, keeping deletion O(1).

LRU Cache with Hash Map + Doubly Linked List

For a deep dive into LRU/LFU cache implementations, refer to the Linked List chapter: 06-lru-lfu.md.

Word Pattern (LeetCode 290)

Bi-directional mapping:

boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    if (pattern.length() != words.length) return false;
    
    Map<Character, String> charToWord = new HashMap<>();
    Map<String, Character> wordToChar = new HashMap<>();
    
    for (int i = 0; i < pattern.length(); i++) {
        char c = pattern.charAt(i);
        String w = words[i];
        
        if (charToWord.containsKey(c) && !charToWord.get(c).equals(w)) return false;
        if (wordToChar.containsKey(w) && wordToChar.get(w) != c) return false;
        
        charToWord.put(c, w);
        wordToChar.put(w, c);
    }
    return true;
}