Create a gist now

Instantly share code, notes, and snippets.

# Code Dojo 20160913
# Problem is from HackerRank:
# Joint solution Andrea Heyman, Ivan Vashchenko, Jade Vinson
from collections import Counter
def fast(s):
'''Runs in time 26*n^2.'''
n = len(s)
counts = Counter()
for length in range(1,n):
freq = [0]*26
for i in range(length):
freq[ord(s[i])-97] += 1
counts[tuple(freq)] += 1
for i in range(length,n):
freq[ord(s[i])-97] += 1
freq[ord(s[i-length])-97] -= 1
counts[tuple(freq)] += 1
return sum( v*(v-1)//2 for k,v in counts.items() )
def simple(s):
'''Runtime n^3*log(n), but easier to code.'''
counts = Counter((hash(''.join(sorted(s[i:j+1]))) for i in range(len(s)) for j in range(i,len(s))))
return sum( v*(v-1)//2 for v in counts.values() )
num_cases = int(input())
for i in range(num_cases):
s = str(input())
nfast = fast(s)
assert(nfast == simple(s))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment