Permutation in String LeetCode Solution: Fixed-Size Sliding Window

Permutation in String (#567) is one of the cleanest examples of the fixed-size sliding window pattern on LeetCode. It asks a simple question: does any substring of s2 with length equal to s1 have the exact same character frequency as s1? If yes, that substring is a permutation of s1.

This problem sits at the intersection of two fundamental techniques — sliding windows and frequency counting. Once you recognize that checking for a permutation is the same as checking for matching character frequencies, the brute-force impulse to generate all permutations disappears entirely.

The permutation in string leetcode problem is also a direct stepping stone to harder problems like Minimum Window Substring (#76). Master the fixed-size version here, and the variable-size version becomes much more approachable.

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise. In other words, return true if one of s1's permutations is a substring of s2.

The key insight is reframing the question. Instead of asking "does any permutation of s1 appear in s2?" you ask "does any substring of s2 of length len(s1) have the same character frequency as s1?" These two questions are mathematically identical because two strings are permutations of each other if and only if they share the same character counts.

This reframing is what makes the leetcode 567 solution tractable. Generating all permutations of s1 would be O(n!) — impossibly slow for any meaningful input. Checking frequency equivalence for each window is O(26) per step, which is effectively constant.

The sliding window permutation approach works because the window size is fixed at len(s1). You slide a window of exactly that size across s2, one character at a time. At each position, you check whether the character frequencies inside the window match the frequencies of s1.

Here is the high-level strategy. First, count the frequency of every character in s1. Then initialize a window of the same size at the start of s2 and count its frequencies. If they match, return true immediately. Otherwise, slide the window right by one position — add the new right character and remove the leftmost character — and check again.

The fixed size sliding window means you never need to shrink or grow the window conditionally. Every step adds exactly one character on the right and removes exactly one on the left. This predictability is what makes the pattern simpler than variable-size sliding window problems.

The implementation uses two frequency arrays of size 26 (one for each lowercase letter). The first array counts s1. The second tracks the current window in s2. You initialize the window with the first len(s1) characters of s2, then slide right one character at a time.

On each slide, increment the count for the new character entering the window on the right, and decrement the count for the character leaving on the left. Then compare the two arrays. If they are identical, you have found a permutation and return true.

Comparing two arrays of size 26 on every step gives O(26 * n) total work, which simplifies to O(n). Space is O(1) since the frequency arrays are always size 26 regardless of input length. This is optimal — you cannot do better than examining each character at least once.

Let us trace through s1 = "ab" and s2 = "eidbaooo". The window size is 2. The frequency of s1 is {a:1, b:1}. We check each window of size 2 in s2.

Window "ei" at index 0-1: frequencies are {e:1, i:1}. No match. Slide right. Window "id" at index 1-2: {i:1, d:1}. No match. Slide right. Window "db" at index 2-3: {d:1, b:1}. No match. Slide right.

Window "ba" at index 3-4: frequencies are {b:1, a:1}. This matches {a:1, b:1} exactly — "ba" is a permutation of "ab". Return true. We found the anagram substring in just 4 window checks.

Notice we never generated any permutations of "ab". We never checked "ab" and "ba" as separate strings. We simply compared character counts, which is the entire trick behind the sliding window permutation approach.

The most important edge case is when s1 is longer than s2. If len(s1) > len(s2), no window of size len(s1) can fit inside s2, so the answer is immediately false. Always check this before entering the main loop.

When s1 equals s2, the answer is trivially true — the entire string is its own permutation. When s1 is a single character, you are simply checking if that character appears anywhere in s2, which the window approach handles naturally.

Another subtle case: when all characters in s1 are the same, like s1 = "aaa". The window must contain exactly three a's. The frequency approach handles this correctly without any special logic, since the count array for s1 would be {a:3} and only a window with three consecutive a's would match.

This problem crystallizes the fixed-size sliding window pattern with frequency matching. The same technique applies to Find All Anagrams in a String (#438), which is essentially the same problem but asks you to return all starting indices instead of just true/false.

It also teaches the critical skill of problem reframing. The word "permutation" triggers thoughts of factorial complexity, but reframing to "frequency equivalence" collapses the problem to linear time. This kind of insight is exactly what interviewers want to see.

The character frequency window pattern appears across many LeetCode problems at varying difficulty levels. Once you internalize it here with the fixed-size version, you are ready for the variable-size version in Minimum Window Substring (#76) and other advanced sliding window problems. Review this pattern regularly with YeetCode flashcards to keep it sharp for your next interview.