[해커랭크] Sherlock and Anagrams (C++)

문제 링크: www.hackerrank.com/challenges/sherlock-and-anagrams/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

Sherlock and Anagrams | HackerRank

1. 주의할 점

- substring 길이에 따라 다른 Map에 저장한다

- 정렬을 이용한다

 

2. 구현

- 최대 길이 100까지 담을 수 있는 Map[]을 생성한다. Map은 <substring, substring 출현 개수> 형태로 저장한다

- 문자열 S에서 뽑아낼 수 있는 모든 substring ss를 정렬한 이후, Map에 추가한다

- Map에 포함된 모든 원소중에서 두 번째 인자 n이 2 이상일 때, nC2를 Result에 추가한다(조합의 개수만큼 더한다)

int sherlockAndAnagrams(string s) {
    int len = s.size();
    int result = 0;
    map<string, int> m[101];
    for(int i=0;i<len;i++){
        string ss="";
        for(int k=i;k<len;k++){
            ss+=s[k];
            sort(ss.begin(),ss.end());
            int t = ss.size();
            if(m[t].find(ss)==m[t].end())
                m[t][ss]=1;
            else m[t][ss]++;
        }
    }
    for(int k=1;k<len;k++){
        for(auto it = m[k].begin(); it!=m[k].end();it++){
            int cnt = it->second;
            if(cnt>1){
                result +=(cnt-1)*cnt/2;
            }
        }
    }
    return result;
}