567. Permutation in String

Quick Identifier

• Topic: sliding-window
• Pattern: Sliding Window (Fixed Window + Frequency Match)
• Hint: A "permutation" is just an anagram. You need to find if any substring in s2 is an anagram of s1. Use a fixed window of size s1.length.
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Microsoft, Adobe
• LeetCode: 567

Quick Sights

• Time Complexity: O(n). We initialize the frequency arrays in $O(m)$ time (where $m$ is the length of s1). We then slide a window across s2 (length $n$), taking $O(1)$ per step. Checking array equality takes $O(26) = O(1)$. Overall time is strictly linear.
• Space Complexity: O(1). We allocate two arrays of size 26 for counting lowercase English letters.
• Core Mechanism: Because a permutation of s1 must have exactly the same length as s1, our window size is rigidly fixed. For every shift to the right, we add the incoming character's frequency and decrement the outgoing character's frequency. If the two frequency arrays match exactly, we immediately return true.

Concept Explanation

As a senior engineer, whenever you see "permutation of a substring", your brain should instantly translate that to "multiset equality over a fixed window". The actual order of characters in s1 is a distraction; we only care about the ingredients (character counts).

1. The Recipe: Count the exact ingredients needed to bake s1. Since the problem guarantees lowercase English letters, a 26-slot integer array is the fastest data structure.
2. The Fixed Baking Tin: Create a "baking tin" (sliding window) that is exactly the size of s1. Any smaller or larger, and it's mathematically impossible to be a permutation.
3. The Conveyor Belt: Place the tin over the start of s2.
   • Does the mix inside the tin match the recipe? If yes, return true.
   • If no, slide the tin exactly one slot to the right. One ingredient falls out of the left side (decrement count), and one new ingredient enters from the right (increment count).
   • Check the recipe again.
   • If the tin falls off the conveyor belt without ever matching the recipe, return false.

Diagram

This flowchart outlines the $O(1)$ rolling update of the fixed-size sliding window.

Study Pattern (SDE3+)

• 0–3 min: Immediately point out that this is identical to LeetCode 438: Find All Anagrams in a String, but we just return a boolean on the first match instead of accumulating indices. State the $O(n)$ time bounds.
• Implementation pass: Use the sliding window initialization pattern carefully. Check the 0th window before the loop, then start the loop at index s1.length to manage the rolling updates cleanly.
• 5 min extension: Discuss how to optimize the equality check further. Instead of an $O(26)$ array comparison, you can maintain an integer matches representing how many characters have the exact same frequency. When matches == 26, you have a valid permutation. This drops the constant factor heavily.

Approaches

• Brute force — For every index, extract substring of length s1.length, sort it, and compare to sorted s1. Time: $O(n \cdot m \log m)$.
• Optimized Sliding Window — Sliding window with size-26 integer arrays. Direct array comparison a == b in Go, or a short loop in JS. Time: $O(n \cdot 26) = O(n)$. (Pick this)
• Ultra-Optimized Window — Sliding window tracking a single matches integer (0 to 26). Time: $O(n)$ with minimal constant factor. (Great to talk about, harder to code bug-free under pressure).

Optimal Solution

Go

func checkInclusion(s1 string, s2 string) bool {
	if len(s1) > len(s2) {
		return false
	}
	
	want := [26]int{}
	window := [26]int{}
	
	// Initialize target and the first window
	for i := 0; i < len(s1); i++ {
		want[s1[i]-'a']++
		window[s2[i]-'a']++
	}
	
	// Check the very first window
	if window == want {
		return true
	}
	
	// Slide the window character by character
	for right := len(s1); right < len(s2); right++ {
		window[s2[right]-'a']++               // Add incoming character
		window[s2[right-len(s1)]-'a']--       // Remove outgoing character
		
		if window == want {
			return true
		}
	}
	
	return false
}

JavaScript

function checkInclusion(s1, s2) {
	if (s1.length > s2.length) return false;
	
	const want = new Array(26).fill(0);
	const window = new Array(26).fill(0);
	
	// Initialize frequencies
	for (let i = 0; i < s1.length; i++) {
		want[s1.charCodeAt(i) - 97]++;
		window[s2.charCodeAt(i) - 97]++;
	}
	
	if (arraysEqual(window, want)) return true;
	
	// Slide the window
	for (let right = s1.length; right < s2.length; right++) {
		window[s2.charCodeAt(right) - 97]++;
		window[s2.charCodeAt(right - s1.length) - 97]--;
		
		if (arraysEqual(window, want)) {
			return true;
		}
	}
	
	return false;
}

function arraysEqual(a, b) {
	for (let i = 0; i < 26; i++) {
		if (a[i] !== b[i]) return false;
	}
	return true;
}

Walkthrough

Input: s1 = "ab", s2 = "eidbaooo" (Lengths: s1 = 2, s2 = 8) want = [a:1, b:1]

Output: true

Edge Cases

• s1 is longer than s2 (Immediately return false).
• Both strings are exactly the same length.
• Permutation exists at the very end of s2.

Pitfalls

• Not handling the very first window comparison before the loop. If the permutation is right at the start (e.g. s1="ab", s2="aba"), and you only check inside the loop after sliding, you will miss the index 0 match.
• Using s2.slice().split().sort().join() to check anagrams inside the loop—this transforms an $O(n)$ solution into an $O(n \cdot m \log m)$ timeout disaster.

Similar Problems

• 438. Find All Anagrams in a String — The exact same algorithm, but it accumulates all valid start indices instead of returning immediately.
• 076. Minimum Window Substring — Variable window where the target is a subset, not an exact length match.

Mind-Map Tags

#sliding-window #fixed-window #anagram #frequency-vector #lowercase-english