Sliding Window + Strings (Minimum Window, Permutations)

Minimum Window Substring (LeetCode 76)

Find the smallest substring in s that contains all characters in t.

Template: Sliding Window

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, r = 0, valid = 0;
    int start = 0, minLen = Integer.MAX_VALUE;

    while (r < s.length()) {
        char c = s.charAt(r++);
        // Expand the window
        if (need.containsKey(c)) {
            window.merge(c, 1, Integer::sum);
            if (window.get(c).equals(need.get(c))) valid++;  // One character requirement fully met
        }
        
        // Attempt to shrink the window
        while (valid == need.size()) {
            if (r - l < minLen) { 
                minLen = r - l; 
                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);
}

Permutation in String / Find All Anagrams (LeetCode 567 / 438)

Fixed Window Size = t.length(), slide the window across:

// 567: Check if s2 contains a permutation of s1
boolean checkInclusion(String s1, String s2) {
    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']--;  // Slide the window (pop left)
        if (Arrays.equals(need, window)) return true;
    }
    return false;
}

// 438: Find all start indices of anagrams
List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    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)) res.add(i - k + 1);
    }
    return res;
}

Longest Substring Without Repeating Characters (LeetCode 3)

Dynamic Window:

int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>(); // character -> latest index
    int l = 0, maxLen = 0;
    for (int r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        // If we see the character again, jump the left pointer forward
        if (map.containsKey(c)) {
            l = Math.max(l, map.get(c) + 1);
        }
        map.put(c, r);
        maxLen = Math.max(maxLen, r - l + 1);
    }
    return maxLen;
}

Longest Substring with At Most K Distinct Characters (LeetCode 340)

int lengthOfLongestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> freq = new HashMap<>();
    int l = 0, maxLen = 0;
    for (int r = 0; r < s.length(); r++) {
        freq.merge(s.charAt(r), 1, Integer::sum);
        // Shrink while distinct character count exceeds K
        while (freq.size() > k) {
            char leftChar = s.charAt(l++);
            freq.merge(leftChar, -1, Integer::sum);
            if (freq.get(leftChar) == 0) freq.remove(leftChar);
        }
        maxLen = Math.max(maxLen, r - l + 1);
    }
    return maxLen;
}

Summary of the Sliding Window Template

Iterate with 'right' to expand window until condition met
└─ If met:
   ├─ Update answer (when window is at its most optimal)
   └─ Move 'left' to shrink window as much as possible
Slide until condition is lost
└─ Resume expanding 'right'