Bloomberg L.P.

www.bloomberg.com
Engaged Employer

Interview

# Counting the number of anagrams of one string in another

string

0

Not thought deeply so maybe there is a better performance solution but by utilising existing is_anagram function, something following would work at C++. template &lt;typename T, typename K&gt; bool is_anagram(T &&str1, K &&str2) { map&lt;char, int&gt; hmap; for(auto &ch: str1) { if(ch!='\0') hmap[ch]++; } for(auto &ch: str2) { if(ch!='\0') hmap[ch]--; } for(auto &pr:hmap) { if(pr.second!=0) { return false; } } return true; } template &lt;typename T, typename K&gt; int count_anagrams(T && base, K&& target) { int count = 0; size_t len_target = target.size(); size_t len_base = base.size(); for(int i=0; i&lt;=len_base-len_target; ++i) { if(is_anagram(base.substr(i, len_target), std::forward&lt;K&gt;(target))) count ++; } return count; } int main() { cout &lt;&lt; count_anagrams("str1strstr", "str") &lt;&lt; endl; return 0; }

goktan on Jul 28, 2014
0

there is a quick way to do it. 1. use a hashtable to calculate counts for each character in first string (str1), say it's int count1[256] (assume characters are ASCII codes here), this takes O(length of str1) 2. traverse through second string (str2), for each index i, if count[str2[j]] is not 0, we know this character is in str1, calculate another hashtable count2[] between index i and (i+len of str1) (assume i + len of str 1 is still within boundary) , if count2[] and count1[] are identical then one anagram is found. this takes O( len of str 2 * len of count1)

gallon on Dec 31, 2014