Four windows, four invariants

Longest substring without repeating characters

Recognize it from

Longest (or shortest) contiguous substring where every character is unique. Wording like “no duplicate in the window,” “at most one of each,” or “longest valid slice under a shrinking rule.” If they allow holes, it is a subsequence and this loop is the wrong tool.

What it actually does

right walks every index once and always includes s.charAt(right). The window [left, right] is the longest suffix of the prefix s[0..right] that has unique characters. A HashMap stores the last index where each character appeared. When the character at right was already inside the current window, left jumps to one past that last index.

The jump is legal because any start between the old left and that last index still contains the duplicate. Characters whose last index is before left are already outside the window — their map entry is stale. That is why the interview block guards with lastSeen >= left instead of blindly setting left = lastSeen + 1.

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> last = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        // last.getOrDefault(..., -1)+1 is 0 when c is new, so max keeps left still
        left = Math.max(left, last.getOrDefault(c, -1) + 1);
        last.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.isEmpty()) return 0;
    Map<Character, Integer> last = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        Integer lastSeen = last.get(c);
        // stale lastSeen < left is outside the window — do not pull left backward
        if (lastSeen != null && lastSeen >= left) {
            left = lastSeen + 1;
        }
        last.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Example 1 — simple

Input s = "abca". Four characters, one repeat at the end.

Answer 3 — windows abc and bca both have length 3.

Example 2 — every step

Input s = "abcabcbb". Watch left jump on every repeat, including the two trailing bs.

Answer 3. The interesting jump is right=7: last b is at 6, which is still inside [5,6], so left becomes 7. If you wrote left = lastSeen + 1 with no guard on a string like "abba", left would move backward when a stale a is seen after the window has already passed it.

Notebook problems for this topic

Find all anagrams — fixed window

Recognize it from

Every start index where a substring of s is an anagram of p. Window length is locked at p.length(). Same letters, any order. Not “group anagrams of a word list” (that is a map of sorted keys) and not “exactly K distinct.”

What it actually does

A fixed window of width m = p.length() slides one character at a time. After the first m characters, each step adds s[i] and removes s[i − m]. The window is an anagram when its letter bag equals p’s letter bag.

Sorting each slice makes the idea visible and is too slow. The interview loop keeps two int[26] arrays (or one deficit array) and a single missing / match counter so you do not scan 26 letters every step.

public List<Integer> findAnagrams(String s, String p) {
    char[] need = p.toCharArray();
    Arrays.sort(need);
    String key = new String(need);
    List<Integer> ans = new ArrayList<>();
    int m = p.length();
    for (int i = 0; i + m <= s.length(); i++) {
        // sort copies the window — O(m log m) per start, so you feel the waste
        char[] w = s.substring(i, i + m).toCharArray();
        Arrays.sort(w);
        if (key.equals(new String(w))) ans.add(i);
    }
    return ans;
}

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> ans = new ArrayList<>();
    if (s == null || p == null || s.length() < p.length()) return ans;
    int[] need = new int[26];
    for (int i = 0; i < p.length(); i++) need[p.charAt(i) - 'a']++;
    int missing = p.length();
    int m = p.length();
    for (int i = 0; i < s.length(); i++) {
        int in = s.charAt(i) - 'a';
        // need[c] > 0 means this copy of c is still owed to p
        if (need[in] > 0) missing--;
        need[in]--;
        if (i >= m) {
            int out = s.charAt(i - m) - 'a';
            need[out]++;
            // after restore, > 0 means we now owe that letter again
            if (need[out] > 0) missing++;
        }
        if (i >= m - 1 && missing == 0) ans.add(i - m + 1);
    }
    return ans;
}

Example 1 — simple

Input s = "cba", p = "abc". One window, sort both sides.

Answer [0].

Example 2 — every step

Input s = "cbaebabacd", p = "abc". Every slide of width 3. Interview column is the missing counter after add (and remove when i ≥ 3).

Answer [0, 6] — cba and bac. Sort-every-window agrees: only those two slices sort to abc.

Notebook problems for this topic

Exactly-K via atMost(K) − atMost(K−1)

Recognize it from

Count of subarrays with exactly K odds, exactly K distinct, exactly K zeros, and so on. The resource is a 0/1 budget (or a distinct-count budget) and values do not go negative in a way that breaks monotonicity. If they want an exact sum and the array can contain negatives, that is prefix + HashMap, not this subtract.

What it actually does

“Exactly K” is not monotone: adding one more odd can take you from K to K+1. “At most K” is monotone: once you have too many odds you must shrink, and you never want those discarded left indices back. For each right end, after shrinking, every left in [left, right] is a valid at-most-K window ending at right — there are right − left + 1 of them.

Then exactly(K) = atMost(K) − atMost(K−1). Nice subarrays: odd → 1, even → 0, K odds. The simple block is only atMost so you can see the engine. The interview block subtracts. Guard k < 0 so atMost(K−1) is 0 when K is 0.

public int atMostOdd(int[] a, int k) {
    if (k < 0) return 0;
    int left = 0, odd = 0, ans = 0;
    for (int right = 0; right < a.length; right++) {
        if ((a[right] & 1) == 1) odd++;
        while (odd > k) {
            // evens do not change odd, but they still leave the window
            if ((a[left] & 1) == 1) odd--;
            left++;
        }
        // every [l, right] with l in [left, right] has ≤ k odds
        ans += right - left + 1;
    }
    return ans;
}

public int numberOfSubarrays(int[] a, int k) {
    // exactly k = (windows with ≤ k) minus (windows with ≤ k−1)
    return atMostOdd(a, k) - atMostOdd(a, k - 1);
}

private int atMostOdd(int[] a, int k) {
    if (k < 0) return 0;
    int left = 0, odd = 0, ans = 0;
    for (int right = 0; right < a.length; right++) {
        odd += a[right] & 1;
        while (odd > k) odd -= a[left++] & 1;
        ans += right - left + 1;
    }
    return ans;
}

Example 1 — simple

Input a = [1, 1, 2], k = 1. Dry-run atMost(1) only — that is the simple method.

atMost(1) = 4 windows: [1], [1] (index 1), [1,2], [2]. That is not the nice-subarray answer. Exactly 1 odd is 3 of those four (drop the even singleton). Interview subtracts atMost(0) = 1 → 3.

Example 2 — every step

Input a = [1, 1, 2, 1, 1], k = 3. Both atMost values, every right.

14 − 12 = 2. The two subarrays with exactly 3 odds are [1,1,2,1] (indices 0..3) and [1,2,1,1] (indices 1..4).

Notebook problems for this topic

Sliding window maximum — monotonic deque

Recognize it from

Max (or min) of every contiguous window of width K. Story wrap: “max of each k days,” warehouse / delivery dressing. Same deque lives in the stacks chapter; keep the full card here because the loop is a sliding window of indices.

What it actually does

A brute scan of each window is O(nk). The interview structure is an ArrayDeque of indices, with values decreasing from front to back. The front is the current max. When index i arrives: drop the front if it is ≤ i − k (it left the window); drop the back while a[back] ≤ a[i] (those values can never be max while i is still in the window); push i. Once i ≥ k − 1, record a[front].

Each index is pushed and popped at most once, so the extra work is O(n), not O(nk). Store indices, not values — otherwise you cannot tell a duplicate max that has already slid out.

public int[] maxSlidingWindow(int[] a, int k) {
    int n = a.length;
    int[] ans = new int[n - k + 1];
    for (int i = 0; i + k <= n; i++) {
        int m = a[i];
        // rescan k−1 shared cells every step — that is why this is O(nk)
        for (int j = i + 1; j < i + k; j++) m = Math.max(m, a[j]);
        ans[i] = m;
    }
    return ans;
}

public int[] maxSlidingWindow(int[] a, int k) {
    if (a == null || a.length == 0 || k <= 0) return new int[0];
    int n = a.length;
    int[] ans = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>(); // indices, a[idx] decreasing
    for (int i = 0; i < n; i++) {
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) {
            // last can never beat a[i] while i is still in the window
            dq.pollLast();
        }
        dq.offerLast(i);
        if (i >= k - 1) ans[i - k + 1] = a[dq.peekFirst()];
    }
    return ans;
}

Example 1 — simple

Input a = [1, 3, −1], k = 3. One window, so brute and deque agree.

Answer [3].

Example 2 — every step

Input a = [1, 3, −1, −3, 5, 3, 6, 7], k = 3. Every index of the deque, no skipped i.

Answer [3, 3, 5, 5, 6, 7]. At i=4 the expired 3 at index 1 would have been wrong if you stored values and could not tell it had left.

Notebook problems for this topic

See also on this chapter

Anagrams, nice subarrays, and window max share chapter 05 / 24 / R4 cards already linked on their own blocks. Complete-subarrays and the repeating-character replacement variation sit on the variable-window card. Srenitha’s leftover-hour prompt is UNNAMED — lock their predicate before you type last-seen or deque. Rotten oranges is linked above so you do not reach for a window when the grid is rotting by BFS layers.