Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a substring. Strings contain only lowercase English letters.

You can solve this with a fixed-size sliding window of length len(s1).

Why this is worth learning

For a fixed-length window, equality of frequency vectors is exactly multiset equality. No ordering information is needed to recognize a permutation.

Before coding: one-minute experiment

Why does pattern "aab" not match window "abb", even though both contain only a and b?

Function signature

func CheckInclusion(s1 string, s2 string) bool

Inputs / outputs

• s1: pattern string.
• s2: search string.
• Return: true if any permutation of s1 appears in s2.

Example

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

Substring "ba" is a permutation of "ab".

Constraints

• 0 <= len(s1), len(s2) <= 100_000
• Strings contain only lowercase letters.

Core idea (near-solution)

A permutation has the same character counts. Use a sliding window of length len(s1) over s2 and compare 26-letter counts.

Invariant: the window always has length len(s1) and its counts reflect exactly its contents.

Algorithm (step-by-step)

1. If len(s1) > len(s2), return false.
2. Build 26-count arrays for s1 and for the first window in s2.
3. If counts match, return true.
4. Slide the window one character at a time:
   • Add the new right character.
   • Remove the old left character.
   • If counts match, return true.
5. Return false.

Correctness sketch

A permutation of s1 has the same length and the same multiplicity of every lowercase letter. Build its 26-count vector and maintain the vector for the current equally sized substring of s2. Moving one step removes exactly the leaving byte and adds exactly the entering byte, so induction keeps the counts correct. Equality of all 26 coordinates is necessary and sufficient for the window to be a permutation. Scanning every possible start therefore finds a match exactly when one exists. The empty pattern matches an empty window, so it returns true; a longer pattern than text cannot match.

Trace (hand walkthrough)

Example input:
s1 = "ab", s2 = "eidbaooo"
Output: true

Substring "ba" is a permutation of "ab".

Walk:
- window "ei" counts != "ab"
- slide: "id" !=
- slide: "db" !=
- slide: "ba" matches -> true

Pitfalls to avoid

• Forgetting to keep the window length fixed.
• Comparing counts incorrectly (must be equal for all 26 letters).

Debugging lens

Test empty patterns, patterns longer than the text, repeated letters, and matches at the final possible start. A frequency vector must count duplicates, not only presence.

Complexity

Time: O(len(s1)+len(s2)) for the fixed 26-letter alphabet. Auxiliary space: O(1).

Implementation notes (Go)

• Use fixed-size [26]int counts for lowercase letters.
• Update counts for entering/leaving chars; check only when window size matches.

Contract precision

An empty s1 is considered a permutation appearing at an empty boundary and returns true, including when both strings are empty.

Reconstruction checkpoint

Why does pattern "aab" not match window "abb", even though both contain only a and b?

Return to Sliding Window · Module quiz