Permutation in String — Fixed Window Anagram Matching

Problem Statement#

Given two strings s1 and s2, return true if s2 contains any permutation of s1 as a substring. In other words, check if any rotation of letters in s1 appears contiguously inside s2.

Constraints:

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

Input:  s1 = "ab", s2 = "eidbaooo"
Output: true

Input:  s1 = "ab", s2 = "eidboaoo"
Output: false

Why This Problem Matters#

LeetCode 567 is a high-frequency phone screen at Google, Amazon, Microsoft, and Bloomberg. It packages two important interview ideas — anagram fingerprints and the fixed-size sliding window — into a single problem you can solve in roughly 20 lines.

Recruiters favor this problem because it has many wrong-but-plausible solutions. Candidates who compare sorted substrings get O(n * m log m), candidates who count characters per window get O(n * 26), and only candidates who maintain a running diff achieve the optimal O(n + m). The gap between solutions reveals depth.

The technique transfers directly to LeetCode 438 (Find All Anagrams in a String) and LeetCode 30 (Substring with Concatenation of All Words). Mastering the fingerprint window once gives you three problems for free.

The Core Insight#

A permutation of s1 is just a multiset of its characters. So s2 contains a permutation of s1 if and only if some window in s2 of length len(s1) has the same character frequency vector.

Instead of comparing two 26-length arrays at every step (O(26) per slide), maintain a single counter matches — the number of letters whose count in the window already equals the count in s1. When matches == 26, the window is a permutation. Each slide updates only two letters, so it adjusts matches in O(1).

The window size is fixed at len(s1), which means right - left + 1 is constant. There is no shrink phase — only a slide.

Visual Dry Run#

Trace s1 = "ab", s2 = "eidbaooo". Need vector [a:1, b:1].

The match is found on the fourth window — the moment all 26 frequency slots align.

Solution (Optimal)#

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
 
        need = [0] * 26
        have = [0] * 26
        for ch in s1:
            need[ord(ch) - ord('a')] += 1
 
        n = len(s1)
        matches = 0
        for i in range(26):
            if need[i] == 0:
                matches += 1
 
        for r in range(len(s2)):
            ri = ord(s2[r]) - ord('a')
            have[ri] += 1
            if have[ri] == need[ri]:
                matches += 1
            elif have[ri] == need[ri] + 1:
                matches -= 1
 
            if r >= n:
                li = ord(s2[r - n]) - ord('a')
                have[li] -= 1
                if have[li] == need[li]:
                    matches += 1
                elif have[li] == need[li] - 1:
                    matches -= 1
 
            if matches == 26:
                return True
 
        return False

var checkInclusion = function (s1, s2) {
    if (s1.length > s2.length) return false;
 
    const need = new Array(26).fill(0);
    const have = new Array(26).fill(0);
    for (const ch of s1) need[ch.charCodeAt(0) - 97]++;
 
    const n = s1.length;
    let matches = 0;
    for (let i = 0; i < 26; i++) if (need[i] === 0) matches++;
 
    for (let r = 0; r < s2.length; r++) {
        const ri = s2.charCodeAt(r) - 97;
        have[ri]++;
        if (have[ri] === need[ri]) matches++;
        else if (have[ri] === need[ri] + 1) matches--;
 
        if (r >= n) {
            const li = s2.charCodeAt(r - n) - 97;
            have[li]--;
            if (have[li] === need[li]) matches++;
            else if (have[li] === need[li] - 1) matches--;
        }
 
        if (matches === 26) return true;
    }
 
    return false;
};

Time: O(n + m) — each character of s2 adds and removes once; each match update is O(1). Space: O(1) — two 26-slot integer arrays.

Common Mistakes#

• Sorting both substrings on every slide. Works but is O(n * m log m).
• Recomputing the full frequency comparison each slide instead of maintaining matches.
• Off-by-one when removing the leftmost character — must use index r - n, not r - n + 1.
• Forgetting to seed matches with the count of zeros in need. Letters that never appear in s1 are already "matched" and stay matched as long as the window also has zero of them.
• Returning true only after the loop ends. Check inside the loop the moment matches == 26.

Interview Tips#

• State up front: "I'll detect anagrams using a fixed window of size len(s1)."
• Explain the matches counter before coding — it is the trick that makes the solution O(1) per slide.
• Sanity-check by walking through both true and false examples.
• If the interviewer hints at scaling beyond ASCII, switch to a HashMap of needs and adjust the threshold from 26 to need.size().
• Mention that the same template solves LC 438 with a one-line change to collect indices.

Follow-up Questions#

• Solve LeetCode 438 (Find All Anagrams). Hint: collect r - n + 1 whenever matches == 26.
• What if characters can be unicode? Hint: HashMap and target the keys-with-positive-need count.
• Find the lexicographically smallest matching window. Hint: store and compare windows on each match.
• What if you may skip up to k characters in s2? Hint: this becomes a more complex DP problem.
• Stream version: s2 arrives one character at a time. Hint: same algorithm — already streaming-friendly.

Key Takeaways#

• LeetCode 567 is a fixed-size sliding window problem.
• Two strings are anagrams when their 26-length character frequency vectors match.
• Maintain a matches counter (number of aligned letters) for O(1) updates per slide.
• Window size equals len(s1); no shrink phase needed.
• Time is O(n + m), space is O(1) for lowercase English letters.
• The same template solves LC 438 (Find All Anagrams) by collecting start indices.
• Common in Google, Amazon, Microsoft, and Bloomberg interview loops.