438. Find All Anagrams in a String #

Problem #

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Problem Summary #

Given a string s and a non-empty string p, find all substrings in s that are Anagrams of p, and return the starting indices of these substrings. Anagrams means having exactly the same characters as a string, just in a different arrangement.

Solution Approach #

This problem tests the “sliding window” technique. It is similar to Problems 3, 76, and 567. The solution also uses freq[256] to record the occurrence frequency of each character. When the left boundary of the sliding window moves to the right, the element passed over releases one count (i.e., count ++); when the right boundary of the sliding window moves to the right, the element passed over consumes one count (i.e., count --). When the difference between the right boundary and the left boundary is len(p), we need to determine whether every element has been used once. The specific approach is: for every element that meets the requirement, count is decremented. The initial value of count is len(p). When every element meets the requirement, and the difference between the right boundary and the left boundary is len(p), count will also equal 0. If there is an element in the interval that does not meet the requirement (freq < 0 or an element that does not exist), then when the interval reaches len(p), count cannot be reduced to 0. When the interval moves right, the left boundary will start count ++ again. Only after the left boundary has moved past these non-conforming elements can count = 0 occur, which means an Anagrams case has been found.

Code #

package leetcode

func findAnagrams(s string, p string) []int {
	var freq [256]int
	result := []int{}
	if len(s) == 0 || len(s) < len(p) {
		return result
	}
	for i := 0; i < len(p); i++ {
		freq[p[i]-'a']++
	}
	left, right, count := 0, 0, len(p)

	for right < len(s) {
		if freq[s[right]-'a'] >= 1 {
			count--
		}
		freq[s[right]-'a']--
		right++
		if count == 0 {
			result = append(result, left)
		}
		if right-left == len(p) {
			if freq[s[left]-'a'] >= 0 {
				count++
			}
			freq[s[left]-'a']++
			left++
		}

	}
	return result
}