http://www.codechef.com/COOK30/problems/MANYCHEF I have verified that my algorithm is correct, and optimal O(N). It is also the same as one mentioned in editorial. Please help me figure out why it TLE’s on the judge. I am aware that Python is significantly slower than C/C++ but there are many C++ solutions which got AC with 0.0x time, and time limit for Python is also 4*Time Limit for C++. Pasting my Python code here.
t = int(raw_input()) chs = 'CHEF' while t > 0: t -= 1 s = raw_input() i = len(s) - 4 r = ['?'] * len(s) while i >= 0: chef = True for j in xrange(4): if chs[j] != s[i+j] and s[i+j]!='?': chef = False if not chef: r[i+3] = ('A' if s[i+3] == '?' else s[i+3]) i -= 1 else: r[i+3] = 'F' r[i+2] = 'E' r[i+1] = 'H' r[i] = 'C' i -= 4 for j in xrange(3+i, -1, -1): r[j]= ('A' if s[j] == '?' else s[j]) print ''.join(r)