I was trying to solve the Longest Common Subsequence problem on a HackerRank exercise. It's quite simple and straightforward, just print out the length of the LCS. I submitted this code:
s1 = raw_input()
s2 = raw_input()
lcs = [[0 for j in xrange(len(s2)+1)] for i in xrange(len(s1)+1)]
for i, x in enumerate(s1):
for j, y in enumerate(s2):
if x == y:
lcs[i+1][j+1] = lcs[i][j] + 1
else:
lcs[i+1][j+1] = max(lcs[i+1][j], lcs[i][j+1])
print lcs[-1][-1]
I think the logic is fine. The maximum string length is 5000. The problem is with the execution time. Some test cases take more than 10 seconds and the program terminates.