solution to https://www.interviewstreet.com/challenges/dashboard/#problem/4eac48496bee2

str_reduc.py

def reduce(s):
    global value, minimum
    l = len(s)
    minimum = l
    if l == 1:
        value = 1
        return True
    elif l == 2 and s[0] == s[1]:
        value = 2
        return True
    for i in range(l - 1):
        if s[i] != s[i + 1]:
            cat = s[0:i] + (set("abc") - set(s[i:i + 2])).pop() + s[i + 2:l]
            if reduce(cat):
                minimum = min(value, minimum)
                return True
    return False
minimum, value, N = 1, 1, int(raw_input())
for _ in xrange(N):
    reduce(raw_input())
    print minimum