Codechef June 2013 Wstring

Seen the editorial, the algorithm described is exactly the same as what I did..but my solution is not accepted. I don't know why ='(

	# 1. partition into substrings separated by #
	# 2. for every substring, create map of symbols and their frequencies
	# 3. for every set of 3 points, from the first 3 to the last 3, compute longest length
	# 4. length for each set of points = longest length for the 4 partitions:
	# a. all partitions, merged as one, before P1
	# b. partition between P1 and P2
	# c. partition between P2 and P3
	# d. all partitions, merged as one, after P3
	# can optimize step 4 by maintaining a map for 4a and 4b each.
	import sys
	def getMaxFrequency(freq):
	maxFreq = 0
	key = -1
	for k in freq.keys():
	if freq[k] > maxFreq:
	maxFreq = freq[k]
	key = k
	return maxFreq
	def compileFrequencies(flist):
	a = {}
	for f in flist:
	for k in f.keys():
	if k in a:
	a[k] += f[k]
	else:
	a[k] = f[k]
	return a
	def minusFrequencies(one, two):
	a = one
	for k in two.keys():
	a[k] -= two[k]
	return a
	T = int(sys.stdin.readline().strip())
	for z in range(T):
	S = sys.stdin.readline().strip()
	# create partitions and frequency dictionary
	partitions = []
	prevIndex = S.find("#")
	frequencies = {}
	for c in S[:prevIndex]:
	if c in frequencies:
	frequencies[c] += 1
	else:
	frequencies[c] = 1
	partitions.append(frequencies)
	while prevIndex != -1:
	nextIndex = S.find("#", prevIndex+1)
	frequencies = {}
	if nextIndex == -1:
	for c in S[prevIndex+1:]:
	if c in frequencies:
	frequencies[c] += 1
	else:
	frequencies[c] = 1
	else:
	for c in S[prevIndex+1:nextIndex]:
	if c in frequencies:
	frequencies[c] += 1
	else:
	frequencies[c] = 1
	#print getMaxFrequency(frequencies)
	partitions.append(frequencies)
	prevIndex = nextIndex
	# cannot have empty partitions
	error = False
	for p in partitions:
	if len(p) == 0:
	error = True
	if len(partitions) < 4:
	error = True
	#print partitions
	if error != True:
	max_length = 0
	allLeft = partitions[0]
	allRight = compileFrequencies(partitions[3:])
	#print allRight
	i = 0
	max_length = 3 + getMaxFrequency(allLeft) + getMaxFrequency(partitions[i+1]) + getMaxFrequency(partitions[i+2]) + getMaxFrequency(allRight)
	for i in range(1,len(partitions)-3):
	# alter allLeft and allRight
	allLeft = compileFrequencies([allLeft, partitions[i]])
	allRight = minusFrequencies(allRight, partitions[i+3])
	length = 3 + getMaxFrequency(allLeft) + getMaxFrequency(partitions[i+1]) + getMaxFrequency(partitions[i+2]) + getMaxFrequency(allRight)
	if length > max_length:
	max_length = length
	#length = 3 + 1
	print max_length
	else:
	print 0

view raw gistfile1.txt hosted with ❤ by GitHub