Permutation in String

1. Problem & Core Objective

The problem

Given two strings s1 and s2, return true if s2 contains a permutation of s1 — that is, if one of s1's permutations appears as a substring of s2.

Input:  s1 = "ab", s2 = "eidbaooo"      Output: true      ("ba" is a permutation of "ab")
Input:  s1 = "ab", s2 = "eidboaoo"      Output: false     ("bo","oa","ao"… none match)

Constraints:

• 1 <= s1.length, s2.length <= 10^4
• s1 and s2 consist of lowercase English letters

What the interviewer is actually testing

This is the fixed-size window — the third of the three templates, and the only one in this section where the window never changes length.

1. Do you translate "permutation" into "identical character counts"? A permutation is a rearrangement, so order is irrelevant and multiplicity is everything. This is Valid Anagram applied to every window.
2. Do you notice the window size is fixed at s1.length()? A permutation of s1 has exactly s1.length() characters, so you never need variable-size logic.
3. Can you make the comparison O(1) instead of O(26)? The matches counter is the refinement, and the incremental reasoning behind it is the interesting part.
4. Do you guard s1.length() > s2.length()? Otherwise the initial window construction runs off the end.

2. First-Principles Thought Process

Step 1 — Constraints

Both strings up to 10^4.

• O(n · m) → 10^8. Borderline; probably passes, but it's not the target.
• O(n · m log m) (sorting each window) → too slow.
• O(n) or O(26n) → the target.

Lowercase English only — so int[26], not a HashMap (06).

Step 2 — Translate the word "permutation"

A permutation of s1 is a rearrangement of exactly its characters. So a substring w of s2 is a permutation of s1 iff:

• w.length() == s1.length(), and
• w and s1 have identical character counts.

That's the anagram condition. So the question becomes:

Does any window of s2 of length s1.length() have the same character counts as s1?

Step 3 — The window size is fixed

This is the key structural observation, and it simplifies everything. Because a permutation has exactly m = s1.length() characters, only windows of exactly that length can match. There is no "expand until valid, then shrink" — the window is always size m, sliding one position at a time.

That makes this Template 1 (fixed size) rather than the longest/shortest-valid templates.

Step 4 — Choose the summary

The window must answer: "do my character counts equal s1's?"

• Two int[26] arrays — one for s1 (fixed), one for the window (updated as it slides).
• Comparison is Arrays.equals(need, window) — 26 comparisons, a constant.

So the straightforward version is O(26n) = O(n). That's already optimal asymptotically, which is worth saying out loud before optimizing further.

Step 5 — The refinement: an incremental matches counter

To make the check genuinely O(1), maintain a counter of how many of the 26 slots currently agree between need and window. Then "is this window a permutation" is matches == 26.

The insight that makes it work:

When you change one slot by ±1, only that slot can change its agreement status.

So after each increment or decrement, you check just that one slot:

• If it just became equal to need → one more slot agrees, matches++.
• If it just moved one step past need (from equal to unequal) → matches--.
• Any other movement doesn't change the status.

Step 6 — The guard

If s1 is longer than s2, no window of size s1.length() exists. The initial construction loop would index past the end of s2 and throw. One line up front:

if (s1.length() > s2.length()) return false;

3. Solution Paths

Approach 1 — Brute force: sort every window

public boolean checkInclusion(String s1, String s2) {
    char[] target = s1.toCharArray();
    Arrays.sort(target);
    int m = s1.length();

    for (int i = 0; i + m <= s2.length(); i++) {
        char[] window = s2.substring(i, i + m).toCharArray();
        Arrays.sort(window);
        if (Arrays.equals(target, window)) return true;
    }
    return false;
}

Sorting canonicalizes each window, so two anagrams compare equal.

• Time: O(n · m log m) — a sort per window.
• Space: O(m).

Counter-questions on this approach

⭐ "You sort every window from scratch. What do consecutive windows have in common?"

Almost everything — adjacent windows share m − 1 characters. Only one character leaves and one enters. Re-sorting rebuilds information I already had, which is the signal to maintain the summary incrementally instead.

"Why sort at all, when you only need counts?"

Sorting produces a total ordering when a multiset comparison is strictly weaker — the same argument as in Valid Anagram. Counting is O(m) per window instead of O(m log m), and incremental counting is O(1).

Approach 2 — Fixed window with count arrays

public boolean checkInclusion(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    if (m > n) return false;                       // no window of that size exists

    int[] need = new int[26], window = new int[26];
    for (int i = 0; i < m; i++) {                  // build s1's counts and the first window
        need[s1.charAt(i) - 'a']++;
        window[s2.charAt(i) - 'a']++;
    }
    if (Arrays.equals(need, window)) return true;

    for (int right = m; right < n; right++) {
        window[s2.charAt(right) - 'a']++;              // element enters
        window[s2.charAt(right - m) - 'a']--;          // element leaves
        if (Arrays.equals(need, window)) return true;
    }
    return false;
}

How it works. Build both count arrays for the first window, then slide: add the entering character, remove the leaving one, compare.

Trace on s1 = "ab", s2 = "eidbaooo" (m = 2):

The leaving index is right - m. For right = 4 and m = 2, that's index 2 — the character just outside the new window [3, 4]. Verify it on a two-element example before trusting it.

• Time: O(26n) = O(n).
• Space: O(1) — 52 ints.

Counter-questions on this approach

⭐ "You call Arrays.equals on every slide — that's 26 comparisons each time. Is it still O(n)?"

Yes. 26 is a constant fixed by the problem's alphabet, not a function of the input, so O(26n) is O(n). It's a real constant factor and it can be removed, but the asymptotic claim is already correct — I'd say so rather than pretending this version is deficient.

⭐ "Why is the window size fixed? Don't you need to expand and shrink?"

Because a permutation of s1 has exactly s1.length() characters. A longer or shorter substring can't be one, so only windows of that size are candidates. That's what makes this the fixed-size template rather than the longest-valid one.

"Why s2.charAt(right - m) for the leaving character?"

After adding the character at right, the window spans [right - m + 1, right], so the character that just fell out is at right - m. It's the standard fixed-window index and the usual off-by-one — worth checking on a concrete case: with m = 2 and right = 4, the window is [3,4] and the departed index is 2.

"What happens if you forget the m > n guard?"

The initial construction loop indexes s2.charAt(i) for i up to m - 1, which exceeds s2's length, and it throws StringIndexOutOfBoundsException. It's not a logic error that produces a wrong answer — it's a crash, and it's the first test case an interviewer will try.

Approach 3 — Incremental matches counter (optimal)

public boolean checkInclusion(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    if (m > n) return false;

    int[] need = new int[26], window = new int[26];
    for (int i = 0; i < m; i++) {
        need[s1.charAt(i) - 'a']++;
        window[s2.charAt(i) - 'a']++;
    }

    int matches = 0;
    for (int i = 0; i < 26; i++) if (need[i] == window[i]) matches++;

    for (int right = m; right < n; right++) {
        if (matches == 26) return true;

        int in = s2.charAt(right) - 'a';                 // entering
        window[in]++;
        if (window[in] == need[in]) matches++;            // just became equal
        else if (window[in] == need[in] + 1) matches--;   // just stopped being equal

        int out = s2.charAt(right - m) - 'a';             // leaving
        window[out]--;
        if (window[out] == need[out]) matches++;
        else if (window[out] == need[out] - 1) matches--;
    }
    return matches == 26;
}

How the increment logic works. After changing one slot by ±1, only that slot's agreement status can change:

For an increment, "one step past" means need + 1; for a decrement, need - 1.

• Time: O(n) — genuinely constant work per slide.
• Space: O(1).

Counter-questions on this approach

⭐ "Why can you check only the one slot you changed, instead of all 26?"

Because a single ++ or -- touches exactly one slot. Every other slot's relationship to need is unchanged, so re-examining them can't reveal anything new. That's the general shape of maintaining a derived invariant incrementally — recompute only what the change could have affected.

⭐ "Why need[in] + 1 for the increment case but need[in] - 1 for the decrement?"

Because "just stopped being equal" means the slot moved away from need by one, and the direction depends on which operation was applied. An increment overshoots to need + 1; a decrement undershoots to need - 1. Getting these backwards makes matches drift and the answer silently wrong.

"Why is the matches == 26 check at the top of the loop rather than the bottom?"

Because the initial window is already built and counted before the loop starts, so its validity must be tested before the first slide. Putting the check at the top covers it. The alternative is an explicit test before the loop plus a check at the bottom — same thing, one more line.

"Is this actually worth the extra complexity over Arrays.equals?"

Honestly, marginally. Both are O(n); this removes a factor of 26. I'd write the Arrays.equals version first because it's obviously correct, and offer this as the refinement — the incremental reasoning is the part worth demonstrating, not the speed.

Comparison

4. Why the Optimal Wins

Against sorting each window. Adjacent windows share m − 1 characters, so re-sorting each one rebuilds information already available. Maintaining counts incrementally reduces per-window work from O(m log m) to O(1).

Against the Arrays.equals version. Both are O(n). The matches counter removes the 26-element scan by noticing that a single-slot change can only affect that slot's agreement. It's a constant-factor win, and I'd say so plainly rather than overselling it — the value is in demonstrating the incremental-invariant technique, which reappears in Minimum Window Substring as the have/need counter.

Why O(n) is the floor. Every character of s2 must be examined, since a matching window could sit anywhere. So O(n) is optimal.

The connection worth naming:

This is Valid Anagram evaluated at every position of s2 — and the sliding window is what makes "at every position" cost O(1) instead of O(m).

5. Java Prerequisites

Fixed-alphabet counting

int[] need = new int[26];
need[c - 'a']++;              // LOWERCASE — base is 'a'

Note this question is lowercase while the previous one was uppercase. Check the constraints rather than copying the base character from the last problem — 'A' vs 'a' is a 32-offset that produces out-of-range indices and throws.

Arrays.equals on primitive arrays

Arrays.equals(need, window);     // element-by-element, O(26) here
need == window                   // reference identity — always false for distinct arrays

Arrays.equals is the static helper. Note it's not what a HashMap would call if you used an array as a key — see 05.

Fixed-window index arithmetic

for (int right = m; right < n; right++) {
    window[s2.charAt(right) - 'a']++;         // entering
    window[s2.charAt(right - m) - 'a']--;     // leaving
}

The departing index is right - m. Derive it rather than memorizing: after adding right, the window is [right - m + 1, right], so the element just outside on the left is right - m.

The length guard

if (s1.length() > s2.length()) return false;

Prevents StringIndexOutOfBoundsException in the initial build loop. Constraints guarantee both are at least 1, so there's no empty-string case, but the length relationship is unconstrained.

charAt vs toCharArray

s2.charAt(i);          // O(1), no allocation

Both ends of the window are indexed independently here, so charAt is the right choice. toCharArray would allocate an O(n) copy for no benefit.

6. Interview Communication Guide

Clarifying questions

1. "Does the permutation need to be a contiguous substring of s2?" — yes. A subsequence version would be a different (and easier) problem.
2. "Are both strings lowercase English only?" — decides int[26] versus a map.
3. "Do I return a boolean, or the index where it occurs?" — boolean here; the index version is a trivial change.
4. "What if s1 is longer than s2?" — return false; confirm so the guard is justified rather than defensive.
5. "Should I find all occurrences, or just whether one exists?" — just existence, which lets me return early.

The pitch

"A permutation of s1 is a rearrangement of exactly its characters, so a substring of s2 is a permutation of s1 if and only if it has the same length and the same character counts. That's the anagram condition applied at every position.

Crucially, the length being fixed means I only ever need windows of exactly s1.length() — so this is a fixed-size window, not an expand-and-shrink one.

I'll build an int[26] for s1 and one for the first window of s2, then slide: add the entering character, remove the leaving one, and compare the arrays. That's O(26n), which is O(n) since 26 is a constant.

To make the comparison genuinely O(1) I can keep a matches counter of how many of the 26 slots currently agree. When I change one slot by one, only that slot's agreement can change — so I adjust matches by inspecting just that slot. The window is a permutation exactly when matches == 26.

One guard up front: if s1 is longer than s2, no window of that size exists and I'd index out of bounds building the first one."

Edge cases to raise proactively

s1 longer than s2 is the one to volunteer — it's a crash, not a wrong answer, and it's the first thing an interviewer will test.

"aa" vs "ab" is the second — it catches solutions using a Set instead of counts, which would see {a} ⊆ {a,b} and wrongly return true. It proves you understood "multiset", not "set".

s1.length() == s2.length() is worth mentioning too: the sliding loop never executes, so correctness depends entirely on checking the initial window.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. ⭐ marks the most likely.

⭐ "Find all starting indices where a permutation of s1 occurs, not just whether one does." (LC 438 — Find All Anagrams in a String)

Nearly the same code: instead of returning true on a match, append right - m + 1 to a result list and keep sliding. Still O(n) time; space becomes O(n) for the output in the worst case. This is the most common escalation, and the two problems are usually asked together.

"What if the alphabet weren't restricted to lowercase English?"

int[26] breaks. Switch to HashMap<Character,Integer> for both counts, and compare with map.equals(map) — or keep the matches idea by tracking the number of satisfied distinct keys, which is exactly the have/need structure in Minimum Window Substring. Space becomes O(k) in the distinct characters.

"What if s1 could contain characters that must appear at least that many times, rather than exactly?"

The window is no longer fixed-size — a valid window could be longer than s1. That converts this into the shortest-valid template, which is precisely Minimum Window Substring. Good illustration that "exactly" versus "at least" is what decides fixed versus variable size.

"What if s2 streams in and you can't index backwards?"

Buffer the last m characters in an ArrayDeque<Character> so you can evict the departing character without indexing the original string. O(m) memory instead of O(1), but it no longer needs random access.

"What if you had to handle q different s1 queries against the same s2?"

Running the window per query is O(q · n). If all queries share the same length m, precompute a rolling count signature for every window of s2 once — O(n) — hash each signature, and answer each query in O(m) by hashing its counts and looking up. Different lengths need one pass per distinct length.

"What if you needed permutations of s1 allowing up to k character substitutions?"

The exact-match condition relaxes to a distance: for each window, the number of substitutions needed is half the sum of absolute differences between the count arrays (each surplus character pairs with a deficit). That's O(26) per window to compute — so O(26n) overall, and the matches shortcut no longer applies.