Table of Contents
Count occurrences of Anagrams
Problem Statement
Anagram is a word, phrase, or sentence formed from another by rearranging its letters.
Given two strings pattern and input.
Find out the number of anagrams of pattern in input.
Example
input := “abc cab a pq bca s acb a yerfxyasz”
pattern := “abc “
Golang Code
package main
import (
"fmt"
)
func countAnagrams(input, pattern string) int {
if len(pattern) > len(input) {
return 0
}
counter := 0
patternMap := make(map[rune]int)
tempMap := make(map[rune]int)
// prepare patternMap
for _, ch := range pattern {
patternMap[ch]++
}
// prepare very first tempMap
j := 0
for j = 0; j < len(pattern); j++ {
tempMap[rune(input[j])]++
}
if match(tempMap, patternMap) {
counter++
}
// now move ahead by incrementing sliding windows
for i, j := 0, len(pattern); i < len(input)-len(pattern); i, j = i+1, j+1 {
//delete(tempMap, rune(input[i]))
tempMap[rune(input[i])]--
if tempMap[rune(input[i])] == 0 {
delete(tempMap, rune(input[i]))
}
tempMap[rune(input[j])]++
if match(tempMap, patternMap) {
counter++
}
}
return counter
}
func match(map1, map2 map[rune]int) bool {
if len(map1) != len(map2) {
return false
}
for key, val := range map1 {
if map2[key] != val {
return false
}
}
return true
}
func main() {
pattern := "abc"
input := "qbacb"
fmt.Println(countAnagrams(input, pattern)) // Output: 3
}
Output
txt := "qbacb"
pat := "abc"
Output: 2
-----------------------
txt := "aaaaa"
pat := "abc"
Output: 0
-----------------------
txt := "aaabcbacabc"
pat := "abc"
Output: 4
-----------------------
txt := "ab"
pat := "abc"
Output: 0
-----------------------
Complexity
- Time Complexity:
- O(n), where n=len(input)n=len(input), as we process each character once.
- Space Complexity:
- O(1), since the maps have a size bounded by the character set.
This implementation is efficient, correct, and handles edge cases appropriately.
Please visit https: https://codeandalgo.com for more such contents
Leave a Reply