Find All Anagrams in a String

1. Problem Description

Given a string s and a non-empty string p, find all substrings in s that are anagrams of p and return their starting indexes.

2. Approach

• Brute force
• Sliding window + counting

3. Implementation

3.1. Brute Force

import "sort"

func findAnagrams(s string, p string) []int {
	if len(s) < len(p) {
		return nil
	}

	pRunes := []rune(p)
	sort.Slice(pRunes, func(i, j int) bool {
		return pRunes[i] < pRunes[j]
	})
	p = string(pRunes)

	res := make([]int, 0)
	sRunes := []rune(s)
	for i := 0; i < len(sRunes)-len(pRunes)+1; i++ {
		dst := make([]rune, len(pRunes))
		copy(dst, sRunes[i:i+len(pRunes)])
		sort.Slice(dst, func(i, j int) bool {
			return dst[i] < dst[j]
		})
		if string(dst) == p {
			res = append(res, i)
		}
	}
	return res
}

3.2. Sliding Window + Counting

func findAnagrams2(s string, p string) []int {
	if len(s) < len(p) {
		return nil
	}

	// Count the occurrences of each letter
	pCnt := make([]int, 26)
	sCnt := make([]int, 26)
	for i := 0; i < len(p); i++ {
		pCnt[p[i]-'a']++
		sCnt[s[i]-'a']++
	}

	// Check whether the first position matches
	res := make([]int, 0)
	if reflect.DeepEqual(sCnt, pCnt) {
		res = append(res, 0)
	}

	// Check the remaining positions
	for i := len(p); i < len(s); i++ {
		sCnt[s[i-len(p)]-'a']--
		sCnt[s[i]-'a']++
		if reflect.DeepEqual(sCnt, pCnt) {
			res = append(res, i-len(p)+1)
		}
	}

	return res

}

4. References

• 438. Find All Anagrams in a String - LeetCode