Permutation in String

Medium

The problem

Given two strings s1 and s2, return true if s2 contains a piece (letters next to each other) that is a rearrangement of s1, using all of its letters exactly once. Otherwise return false.

Example 1
Input: s1 = "abc", s2 = "xxcbaxx"
Output: true
The piece "cba" is a rearrangement of "abc".
Example 2
Input: s1 = "abc", s2 = "acxbxxc"
Output: false
No piece of length 3 has exactly the letters a, b and c.
Example 3
Input: s1 = "ab", s2 = "a"
Output: false
s2 is too short to contain s1's letters.

Limits

1 ≤ s1.length, s2.length ≤ 100,000
Both strings contain only lowercase letters a to z

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

A permutation has the same letter counts. What size must the window always be?

The idea

Slide a fixed-size window (length of s1) over s2, maintaining 26 counts; compare with s1 counts (or track how many letters match).

Target: O(n) time, O(1) space

Go function shape

func checkInclusion(s1 string, s2 string) bool

Reference solution

Tested with go test. Try it yourself first, then compare.

// CheckInclusion: s2 contains a permutation of s1 when some window of len(s1) has the same letter counts.
func CheckInclusion(s1, s2 string) bool {
	if len(s1) > len(s2) {
		return false
	}
	var need, have [26]int
	for i := 0; i < len(s1); i++ {
		need[s1[i]-'a']++
		have[s2[i]-'a']++
	}
	if need == have {
		return true
	}
	for i := len(s1); i < len(s2); i++ {
		have[s2[i]-'a']++         // letter enters on the right
		have[s2[i-len(s1)]-'a']-- // letter leaves on the left
		if need == have {
			return true
		}
	}
	return false
}

Read the lesson: Sliding Window