How to Explain Permutation in String in a Coding Interview (Step-by-Step)
Permutation in String is a fixed-size sliding window problem. The window size is fixed at len(s1) — so there’s no shrinking logic. The challenge is efficiently checking if the window’s character frequencies match s1‘s frequencies as the window slides across s2.
In this post, you’ll learn exactly how to walk an interviewer through this problem: why it’s a fixed-size window, how to track matches efficiently using a matches counter, and the edge cases that catch candidates off guard.
Problem Statement
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.
Examples
Output: true
Explanation: s2 contains “ba” which is a permutation of “ab”
Output: false
Constraints
1 <= s1.length, s2.length <= 10⁴s1ands2consist of lowercase English letters only
What Is the Problem?
“I need to check whether any substring ofs2with the same length ass1is an anagram ofs1. A permutation is just an anagram — same characters, same frequencies, any order.”
Framing it as an anagram check on a sliding window connects it directly to the Valid Anagram pattern — which makes the approach obvious.
Step 1: Start With the Brute Force (Then Dismiss It)
Generate all permutations of s1, check if any is a substring of s2
Time: O(n! · m) — factorial explosion
Space: O(n!)
Sort each window of size len(s1), compare to sorted s1
Time: O(m · n log n)
Space: O(n)
Slide a window of fixed size len(s1) across s2, compare frequency maps in O(1)
Time: O(n + m) Space: O(1) — fixed 26-char alphabet
The Key Insight
Since a permutation has the same length as s1, the window size is fixed at len(s1). This is different from variable-size sliding window problems — we never shrink based on validity. We just slide a fixed-width frame across s2 one character at a time.
At each position, we check if the window’s character frequencies match s1‘s frequencies. To avoid recomputing from scratch each slide, we track the number of characters whose counts match — a matches counter. Adding the new right character and removing the old left character each update matches in O(1).
Step 2: Explain the Algorithm in Plain English
“I build a frequency map fors1and an initial frequency map for the first window ofs2. I count how many of the 26 characters already match between the two maps — that’s mymatchescounter. Ifmatches == 26, the window is a permutation ofs1. Then I slide the window: for each new character added to the right and each character dropped from the left, I update the window’s frequency map and adjustmatchesaccordingly. If at any pointmatches == 26, I returntrue.”
Step 3: Talk Through the Code
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False # s1 can't fit inside s2
# Frequency maps for s1 and the initial window in s2
count1 = [0] * 26
count2 = [0] * 26
n = len(s1)
for i in range(n):
count1[ord(s1[i]) - ord('a')] += 1
count2[ord(s2[i]) - ord('a')] += 1
# Count how many of 26 characters already have matching frequencies
matches = sum(1 for i in range(26) if count1[i] == count2[i])
# Slide the window across s2
for i in range(n, len(s2)):
if matches == 26:
return True # Current window is a permutation of s1
# Add new right character
r = ord(s2[i]) - ord('a')
if count1[r] == count2[r]:
matches -= 1 # Was matching — about to break it
count2[r] += 1
if count1[r] == count2[r]:
matches += 1 # Now matches again
# Remove old left character
l = ord(s2[i - n]) - ord('a')
if count1[l] == count2[l]:
matches -= 1 # Was matching — about to break it
count2[l] -= 1
if count1[l] == count2[l]:
matches += 1 # Now matches again
return matches == 26 # Check the last windowThe matches counter is the key optimisation — instead of comparing all 26 characters every slide, we update in O(1) by only checking the two characters that changed.
Visual Walkthrough
Tracing s1 = "ab", s2 = "eidbaooo". Window size = 2:
Frequency Maps Compared
All 26 characters match → matches == 26 → return true.
Step 4: Highlight Edge Cases
“Iflen(s1) > len(s2), a permutation ofs1can never fit insides2. Returnfalseimmediately. This guard prevents index out-of-bounds errors in the loop.”
“If both strings are equal length, there’s exactly one window to check — the entires2. The initial frequency comparison handles this. If they’re anagrams, we returntrueafter the loop.”
“The loop adds a new character and removes the old one, then the loop ends. The final window is checked in the return matches == 26 at the bottom — not inside the loop. Easy to forget.”
“Ifs1 = "a", we’re looking for any window of size 1 ins2that contains ‘a’. The algorithm works correctly — window size is 1, we slide one character at a time.”
Step 5: State Time and Space Complexity
Let n = len(s1), m = len(s2).
| Dimension | Complexity | Reason |
|---|---|---|
| Time | O(n + m) | O(n) to build initial maps, O(m) to slide the window |
| Space | O(1) | Two arrays of size 26 — fixed alphabet, independent of input size |
“Each character ofs2is added to the window once and removed once. Thematchescounter means each slide is O(1) rather than O(26). Overall O(n + m) time, O(1) space.”
Interview Checklist for Permutation in String
- Restate — “check if any substring of s2 with length len(s1) is an anagram of s1”
- Connect to Valid Anagram — same frequency-matching logic, applied to a sliding window
- State the key insight — fixed window size = len(s1), no shrinking needed
- Explain the
matchescounter — avoids O(26) comparison on every slide - Describe the update logic — check before and after incrementing/decrementing count2
- Handle s1 longer than s2 — early return false
- Handle the last window check —
return matches == 26after the loop - State O(n + m) time and O(1) space
- Ask before coding, don’t just dive in
Related Problems to Practice
If you can solve Permutation in String cleanly, try these next: