HackerRank Sherlock and Anagrams

anargam : 문자열을 재정렬해서 다른 뜻을 가지는 글자로 바꾸는 것

아이디어 : 입력된 문자열의 길이를 length라고 한다. 문자열의 길이를 1~length까지 잘라 나올 수 있는 경우를 모두 구한다. 각 문자열을 정렬해서 dict의 key로 만들고 개수를 누적한다. 누적된 개수로 애너그램을 만들 수 있는 총 개수를 구한다.

1~length까지 cut을 정해놓는다. cut이 길어지는 만큼 for문에서 index i의 최대값을 점점 줄어야하므로 length-count+1 해준다.
잘려진 sub를 dict key로 만들고 누적하기 위해 to_dict를 호출한다.

각 key의 값(n)으로 만들 수 있는 애너그램 조합은 (n-1) + (n-2) ... + 1이다

#!/bin/python3

import os


def sherlock_and_anagrams(s: str):
    length = len(s)
    ana_dict = {}
    cut = 0
    anagrams = 0

    while cut < length:
        cut += 1
        for i in range(0, length - cut + 1):
            sub = s[i:i+cut]
            to_dict(ana_dict=ana_dict, sub=sub)

    for v in ana_dict.values():
        for i in range(1, v):
            anagrams += i

    return anagrams


def to_dict(ana_dict: dict, sub: str):
    sorted_sub = str(sorted(sub))

    if sorted_sub in ana_dict:
        ana_dict[sorted_sub] += 1
    else:
        ana_dict[sorted_sub] = 1


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input().strip())

    for q_itr in range(q):
        s = input()

        result = sherlock_and_anagrams(s=s)

        fptr.write(str(result) + '\n')

    fptr.close()