Intermediate Level
Implement the findAnagramStartCount method that counts starting positions where an anagram of the pattern appears.
The input contains a string text and another string pattern. Your task is to count how many starting positions in text contain an anagram of pattern.
An anagram has the same characters and the same character counts as pattern, but the order may be different.
For example, in cbaebabacd with pattern abc, anagrams start at positions 0 and 6, so the count is 2.
Example 1
Input
text (string) =
cbaebabacdpattern (string) =
abcReturns (int)
2Example 2
Input
text (string) =
ababpattern (string) =
abReturns (int)
3Example 3
Input
text (string) =
abcpattern (string) =
dReturns (int)
0Use the same sliding-window idea as anagram checking, but count every matching window.
The window size should be equal to the length of pattern. Maintain character frequencies for the current window and compare them with the frequencies of pattern.
Every time the two frequency maps match, increase the answer count.
Pseudocode:
function findAnagramStartCount(text, pattern):
m = length of pattern
n = length of text
if m > n:
return 0
patternCount = frequency count of pattern
windowCount = empty frequency map
count = 0
for right from 0 to n - 1:
add text[right] to windowCount
if right >= m:
leftChar = text[right - m]
remove one count of leftChar from windowCount
if right >= m - 1 and windowCount == patternCount:
count++
return countReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run