Bloomberg L.P.

  www.bloomberg.com
  www.bloomberg.com

Interview Question

Financial Software Developer Interview

Counting the number of anagrams of one string in another

  string
Answer

Interview Answer

1 Answer

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 <typename T, typename K>
bool is_anagram(T &&str1, K &&str2) {
    map<char, int> 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 <typename T, typename K>
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<=len_base-len_target; ++i) {
        if(is_anagram(base.substr(i, len_target), std::forward<K>(target))) count ++;
    }
    return count;
}

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

goktan on Jul 28, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.