Example of using memorization

memoi.py

memo_array = {}

def stringReductionHelper(a):
	if len(a) == 1:
		memo_array[1] = (a, 1)
		return memo_array[1]
	if memo_array.get(len(a[:-1])):
		prevChar, prevNum = memo_array.get(len(a[:-1]))
	else:
		prevChar, prevNum = stringReductionHelper(a[:-1])

	if prevChar == a[-1]:
		memo_array[len(a)] = (a[-1], prevNum + 1)
		return memo_array[len(a)]
	else:
		if prevNum % 2 == 1:
			samples = set(['a', 'b', 'c'])
			samples.discard(prevChar)
			samples.discard(a[-1])
			memo_array[len(a)] = (list(samples)[0], 1)
			return memo_array[len(a)]
		else:
			memo_array[len(a)] = a[-1], 1
			return memo_array[len(a)]

#!/usr/bin/py
# Head ends here
def stringReduction(a):
	answer = 0
	char, num = stringReductionHelper(a)
	return num

# Tail starts here
if __name__ == '__main__':
	t = input()
	for i in range(0,t):
		a=raw_input()
		print stringReduction(a)
		memo_array = {} # Reset memo array