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).

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

• Invariant: the window always has length len(s1) and its counts reflect exactly its contents.
• The window state exactly matches the elements in s[l..r].
• Shrinking/expanding preserves validity, so any recorded window is correct.
• The best recorded window is optimal because all candidate windows are considered.

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).

Complexity

• Time: O(n)
• Extra space: O(1) (26 counts).

Implementation notes (Go)

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