[Hackerrank] [Medium] Sherlock and Anagrams

https://www.hackerrank.com/challenges/sherlock-and-anagrams/problem

Sherlock and Anagrams | HackerRank

풀이

• 문자열이 주어졌을 때 anagram의 개수를 구하는 문제
• dictionary를 사용해 substring의 출현 빈도를 count함.
  • key : substring, value : count

def sherlockAndAnagrams(s):
    answer = 0
    substr_dict = {}
    for window_size in range(1, len(s)):
        for start_idx in range(len(s) - window_size + 1):
            # 정렬된 substring을 key값으로 함.
            # s로부터 만들 수 있는 모든 substring을 구해 반복 횟수를 count함.
            substr = "".join(sorted(s[start_idx : start_idx + window_size]))
            if substr in substr_dict.keys():
                answer += substr_dict[substr]
                substr_dict[substr] += 1
            else:
                substr_dict[substr] = 1
    return answer