-
Notifications
You must be signed in to change notification settings - Fork 223
/
sherlock-and-anagrams.py
43 lines (36 loc) · 1.21 KB
/
sherlock-and-anagrams.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#!/bin/python3
import sys
from collections import Counter
from collections import defaultdict
from itertools import permutations
import math
def binomial(x, y):
if y == x:
return 1
elif y == 1: # see georg's comment
return x
elif y > x: # will be executed only if y != 1 and y != x
return 0
else: # will be executed only if y != 1 and y != x and x <= y
a = math.factorial(x)
b = math.factorial(y)
c = math.factorial(x-y) # that appears to be useful to get the correct result
div = a // (b * c)
return div
def get_all_substrings(input_string):
length = len(input_string)
return [input_string[i:j+1] for i in range(length) for j in range(i,length)]
def sherlockAndAnagrams(s):
res = 0
handict = defaultdict(int)
for sub in get_all_substrings(s):
handict[str(sorted(sub))] += 1
#print(list(filter(lambda x: x[1] != 1, handict.items())))
for el in list(filter(lambda x: x[1] != 1, handict.items())):
res += binomial(el[1], 2)
return res
q = int(input().strip())
for a0 in range(q):
s = input().strip()
result = sherlockAndAnagrams(s)
print(result)