567. Permutation in String

At a Glance

Topic: sliding-window
Pattern: Sliding Window
Difficulty: Medium
Companies: Amazon, Google, Meta, Microsoft, Adobe
Frequency: High
LeetCode: 567

Problem (one-liner)

Given strings pattern and stream, return true if any contiguous substring of stream with length len(pattern) is a permutation of pattern (same multiset of letters).

Recognition Cues

Fixed window length = len(pattern)
"Permutation of substring" ↔ multiset equality
Sliding compare of frequency vectors

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — sort every window — O(n * m log m).
Better — rolling frequency difference — O(n) time / O(1) space (26 letters).
Optimal — same with need / formed or diff counter reaching zero.

Optimal Solution

Go

func checkInclusion(pattern string, stream string) bool {
	if len(pattern) > len(stream) {
		return false
	}
	want := [26]int{}
	for index := range pattern {
		want[pattern[index]-'a']++
	}
	window := [26]int{}
	for index := 0; index < len(pattern); index++ {
		window[stream[index]-'a']++
	}
	if window == want {
		return true
	}
	for index := len(pattern); index < len(stream); index++ {
		window[stream[index]-'a']++
		window[stream[index-len(pattern)]-'a']--
		if window == want {
			return true
		}
	}
	return false
}

JavaScript

function checkInclusion(pattern, stream) {
	if (pattern.length > stream.length) {
		return false;
	}
	const want = new Array(26).fill(0);
	for (let index = 0; index < pattern.length; index++) {
		want[pattern.charCodeAt(index) - 97]++;
	}
	const window = new Array(26).fill(0);
	for (let index = 0; index < pattern.length; index++) {
		window[stream.charCodeAt(index) - 97]++;
	}
	if (arraysEqual(window, want)) {
		return true;
	}
	for (let index = pattern.length; index < stream.length; index++) {
		window[stream.charCodeAt(index) - 97]++;
		window[stream.charCodeAt(index - pattern.length) - 97]--;
		if (arraysEqual(window, want)) {
			return true;
		}
	}
	return false;
}

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