Codechef June 2013 Wstring

gistfile1.txt

# 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