Permutation in String

Problem statement

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is a substring of s2.

Example:

Input:

s1 = "ab", s2 = "eidbaooo"

Expected output:

true

Explanation: s2 contains "ba", which is a permutation of "ab".

If you would like to solve the problem on LeetCode, here is the link to the problem: LeetCode problem link

Approach 1: Sliding window + hash maps

Track how many character frequencies currently match between the window and s1. Slide a window of length len(s1) over s2 and return true when every distinct character in s1 is matched.

Time: O(n) where n = len(s2)
Space: O(1) in practice (bounded by distinct characters)

func checkInclusion(s1 string, s2 string) bool {
	if len(s1) > len(s2) {
		return false
	}

	s1Map := make(map[byte]int)
	for i := 0; i < len(s1); i++ {
		s1Map[s1[i]]++
	}

	s2Map := make(map[byte]int)

	found := 0
	i, j := 0, 0

	// Build initial window of size len(s1)-1
	for j < len(s1)-1 {
		ch := s2[j]

		if s2Map[ch] == s1Map[ch] {
			found--
		}

		s2Map[ch]++

		if s2Map[ch] == s1Map[ch] {
			found++
		}

		j++
	}

	// Slide the window
	for j < len(s2) {
		// Add right character
		right := s2[j]

		if s2Map[right] == s1Map[right] {
			found--
		}

		s2Map[right]++

		if s2Map[right] == s1Map[right] {
			found++
		}

		// Check if all frequencies match
		if found == len(s1Map) {
			return true
		}

		// Remove left character
		left := s2[i]

		if s2Map[left] == s1Map[left] {
			found--
		}

		s2Map[left]--

		if s2Map[left] == 0 {
			delete(s2Map, left)
		}

		if s2Map[left] == s1Map[left] {
			found++
		}

		i++
		j++
	}

	return false
}

Approach 2: Sliding window + fixed frequency arrays

Because the alphabet is lowercase English letters, use two [26]int counts. Fill the first window of length len(s1), then slide by adding the incoming character and removing the outgoing one. Array equality means the window is a permutation of s1.

Time: O(n) where n = len(s2) (comparing 26 counts is O(1))
Space: O(1)

func checkInclusion(s1 string, s2 string) bool {
	if len(s1) > len(s2) {
		return false
	}

	var cnt1, cnt2 [26]int

	for i := 0; i < len(s1); i++ {
		cnt1[s1[i]-'a']++
		cnt2[s2[i]-'a']++
	}

	if cnt1 == cnt2 {
		return true
	}

	for i := len(s1); i < len(s2); i++ {
		cnt2[s2[i]-'a']++
		cnt2[s2[i-len(s1)]-'a']--

		if cnt1 == cnt2 {
			return true
		}
	}

	return false
}

Which approach to use?

• Prefer Approach 2 for lowercase a–z input — shorter and clearer.
• Prefer Approach 1 when the alphabet is larger or not limited to 26 letters, or when you want an explicit “matched character count” window pattern (same idea as many anagram sliding-window solutions).