Permutation in String: Fixed-Window Frequency Matching

Permutation in String has a name designed to scare you. "Permutation" whispers factorial — a 10-character s1 has 3,628,800 rearrangements, and generating them all is a dead end you're supposed to notice and reject. The problem is actually about counting, not permuting.

The reframe that cracks it: a permutation is just a multiset of characters. "ab" and "ba" are the same two letters in different orders, so they have identical frequency counts. That one observation turns an explosion of candidates into a single question you can answer in O(1) space: does any window of s2 have the same character counts as s1?

Answering that question efficiently for every window is the fixed-size sliding window pattern — the version where the window never grows or shrinks, it only slides. It's the cleanest introduction to the technique, which is why this problem appears so early in every prep list.

The problem#

Given two strings s1 and s2, return true if s2 contains a substring that is a permutation of s1, and false otherwise. Both strings contain only lowercase English letters.

Two constraints in that statement do the heavy lifting:

• The match must be a contiguous substring — so every candidate has exactly length s1.length. The window size is fixed before you start.
• The alphabet is lowercase English letters only — so a frequency "map" is just an array of 26 integers. No hashing, no dynamic keys.

The brute force baseline#

The honest brute force checks every substring of length s1.length. To test whether one substring is a permutation of s1, sort both and compare:

With n = s2.length and m = s1.length, that's roughly n windows, each paying O(m log m) to sort — O(n · m log m) total. Worse, every window redoes work from scratch: sliding one position changes exactly two characters, yet this code re-extracts and re-sorts all m of them. That redundancy is the smell the optimal solution eliminates. (The truly naive route — generate all m! permutations and indexOf each — is O(m! · n), unusable beyond m ≈ 10.)

The key insight: compare fingerprints, not permutations#

Two strings are permutations of each other if and only if their character frequency counts are identical. So compute s1's frequency array once — call it the fingerprint — and ask each window of s2 whether its fingerprint matches.

The second half of the insight is what makes it O(n): consecutive windows overlap almost entirely. Sliding right by one position removes exactly one character on the left and adds exactly one on the right. Instead of recounting m characters per window, you do two array updates per slide — one decrement, one increment — and the window's fingerprint stays current forever.

This is the fixed window frequency match pattern: fixed window size, incremental count maintenance, equality check per position. The same skeleton solves Find All Anagrams in a String and most "does any window of size k satisfy X" problems.

The optimal solution#

This is the exact algorithm the interactive visualizer steps through — same structure, same variable names:

Read it in three phases. Build: one loop fills both fingerprints — hashS counts all of s1, and hashW counts the first window_length characters of s2, so the first window comes for free. Check: isHashSame compares all 26 slots; a match means the window is a permutation, return true. Slide: decrement the character leaving at i, advance both pointers, increment the character entering at j. The charCodeAt(x) - 97 trick maps 'a'–'z' to indices 0–25, so each update is a single array write.

Note that i and j always sit exactly window_length - 1 apart. The window never resizes — that's what separates this from the variable-size sliding window of problems like Longest Substring Without Repeating Characters, where the pointers move independently.

Walkthrough: s1 = "ab", s2 = "eidbaooo"#

The fingerprint is hashS = {a:1, b:1}, window size 2. Watch hashW evolve as the window slides:

The third row is the instructive one: b already sits at its target count, so the window is half matched — one slide later, a enters as d leaves, completing the fingerprint. The window "ba" is not literally equal to "ab", and that's the whole point: frequency equality is order-blind, which is exactly what "permutation" means.

Complexity#

The 26-slot comparison per window is a constant, but you can shave even that: maintain a matches counter of how many letters currently agree between the two arrays, updating it only for the two letters that change on each slide. That makes each slide O(1) — a nice refinement to mention in an interview after landing the simple version, not a requirement.

Common mistakes#

• Rebuilding the window count from scratch on every slide. Recounting m characters per position gives O(n·m) — the incremental remove-one/add-one update is the entire optimization. If your inner loop touches more than two characters, you've reimplemented the brute force.
• Removing the wrong character. The character that leaves is s2[i] before i advances; the one that enters is s2[j] after j advances. Swap that order and the window drifts off its own frequency array.
• Forgetting the s1 longer than s2 case. No window can exist, so the answer is false. This JavaScript version survives it by accident (j starts beyond the string, so the loop never runs), but in Java, C++, or Rust the build loop will throw — add an explicit if (s1.length > s2.length) return false; guard up front.
• Overrunning on the final slide. After the last window fails its check, j increments past the end of s2 before the loop condition stops it. charCodeAt returns NaN harmlessly in JavaScript; a stricter language will index out of bounds. Check bounds before adding, or restructure as a for loop over the right edge.
• Reaching for a dynamic Map with delete-on-zero. It works, but comparing map sizes and keys is fiddlier than comparing 26 fixed integers. The constraint says lowercase letters — take the array.

Where this pattern shows up next#

Frequency counting and pointer-driven scanning are two of the highest-leverage habits in string and array problems:

• Two Sum — the "remember what you've seen in a hash structure" mindset that frequency arrays specialize.
• Two Sum II - Input Array Is Sorted — two pointers moving over an ordered structure, the sibling technique to sliding windows.
• Is Subsequence — two pointers walking a pair of strings, where order does matter.
• Find the Index of the First Occurrence in a String — the exact-match counterpart: same scan over s2, but the window must equal the pattern character-for-character instead of count-for-count.

You can also step through it interactively to watch the window slide, the two frequency arrays diverge and converge, and the match fire at index 3.

FAQ#

Why compare character frequencies instead of generating permutations?#

Because a permutation is defined by what characters it contains, not where they sit. Two strings are permutations of each other exactly when their character counts are identical, so one 26-integer array captures everything that matters about all m! rearrangements at once. Generating permutations costs O(m!) to answer the question a frequency comparison answers in O(26).

What is the time complexity of the sliding window solution to Permutation in String?#

O(26n), which is O(n) where n is the length of s2. Building the fingerprints costs O(m + 26), and each of the n − m slides does two array updates plus one 26-slot equality check. Space is O(26) = O(1) — two fixed-size arrays regardless of input size.

Why is the window size fixed in this problem?#

Because any permutation of s1 has exactly s1's length — no shorter or longer substring can qualify. That pins the window to size m before the scan starts, so both pointers advance in lockstep and the window only translates, never resizes. Contrast this with variable-size window problems (longest substring with some property), where the right pointer expands and the left pointer contracts independently.

How is Permutation in String different from Find All Anagrams in a String?#

They are the same algorithm with different return types. Permutation in String (LeetCode 567) returns true on the first matching window; Find All Anagrams in a String (LeetCode 438) keeps sliding to the end and collects every matching start index. If you can write one, the other is a two-line edit — swap the early return true for result.push(i).

Can I use a hash map instead of a 26-element array?#

Yes, and for Unicode or mixed-case inputs you'd have to. But with the lowercase-only constraint, the fixed array is strictly better: O(1) indexed access with no hashing, a trivial 26-slot equality check, and no delete-keys-at-zero bookkeeping. Maps earn their keep only when the alphabet is unbounded.