567. Permutation in String #

Problem #

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

1. The input strings only contain lower case letters.
2. The length of both given strings is in range [1, 10,000].

Problem Summary #

Find the position where a substring appears in a string. The substring can exist in the form of Anagrams. Anagrams are all possible permutations and combinations of the characters of a string.

Solution Ideas #

This problem is similar to Problem 438, Problem 3, Problem 76, and Problem 567; the idea used is the “sliding window”.

This problem only needs to determine whether it exists, and does not need to output the starting index of the substring. So this problem is a simplified version of Problem 438. See Problem 438 for the detailed solution idea.

Code #

package leetcode

func checkInclusion(s1 string, s2 string) bool {
	var freq [256]int
	if len(s2) == 0 || len(s2) < len(s1) {
		return false
	}
	for i := 0; i < len(s1); i++ {
		freq[s1[i]-'a']++
	}
	left, right, count := 0, 0, len(s1)

	for right < len(s2) {
		if freq[s2[right]-'a'] >= 1 {
			count--
		}
		freq[s2[right]-'a']--
		right++
		if count == 0 {
			return true
		}
		if right-left == len(s1) {
			if freq[s2[left]-'a'] >= 0 {
				count++
			}
			freq[s2[left]-'a']++
			left++
		}
	}
	return false
}