Bloomberg L.P. Interview Question: Counting the number of anagra... | Glassdoor

Interview Question

Financial Software Developer Interview

Counting the number of anagrams of one string in another


Interview Answer

2 Answers


Not thought deeply so maybe there is a better performance solution but by utilising existing is_anagram function, something following would work at C++.

bool is_anagram(T &&str1, K &&str2) {
    map hmap;
    for(auto &ch: str1) {
    for(auto &ch: str2) {

    for(auto &pr:hmap) {
        if(pr.second!=0) {
            return false;
    return true;

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(target))) count ++;
    return count;

int main() {
    cout << count_anagrams("str1strstr", "str") << endl;
    return 0;

goktan on Jul 28, 2014

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.