Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)

    dp = [[[] for _ in range(M+1)] for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = dp[i][j] + [S[i]]
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], key=len)
    print("".join(dp[N][M]))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    X = input()
    Y = input()
    N = len(X)
    M = len(Y)
    dp = [[0]*(M+1) for _ in range(N+1)]
    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            if x == y:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    res = ""
    while N > 0 and M > 0:
        if dp[N][M] == dp[N-1][M]:
            N -= 1
        elif dp[N][M] == dp[N][M-1]:
            M -= 1
        else:
            res = X[N-1] + res
            N -= 1
            M -= 1
    print(res)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)

    dp = [[""]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = dp[i][j] + S[i]
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], key=len)
    print(dp[N][M])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    X = input()
    Y = input()
    N = len(X)
    M = len(Y)
    dp = [[0]*(M+1) for _ in range(N+1)]
    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            if x == y:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    res = ""
    while N > 0 and M > 0:
        if dp[N][M] == dp[N-1][M]:
            N -= 1
        elif dp[N][M] == dp[N][M-1]:
            M -= 1
        else:
            res = X[N-1] + res
            N -= 1
            M -= 1
    print(res)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)

    dp = [[""]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = dp[i][j] + S[i]
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], key=len)
    print(dp[N][M])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    X = input()
    Y = input()
    N = len(X)
    M = len(Y)
    dp = [[0]*(M+1) for _ in range(N+1)]
    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            if x == y:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    res = ""
    while N > 0 and M > 0:
        if dp[N][M] == dp[N-1][M]:
            N -= 1
        elif dp[N][M] == dp[N][M-1]:
            M -= 1
        else:
            res = X[N-1] + res
            N -= 1
            M -= 1
    print(res)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main(X, Y):
    M = len(Y)
    dp = [0]*(M+1)
    dp_s = [""]*(M+1)
    for i, x in enumerate(X):
        dp_pre = dp[:]
        dp_s_pre = dp_s[:]
        for j, y in enumerate(Y):
            if x == y:
                dp[j+1] = dp_pre[j] + 1
                dp_s[j+1] = dp_s_pre[j] + x
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
                dp_s[j+1] = dp_s[j]
    return print(dp_s[M])


if __name__ == "__main__":
    X = input()
    Y = input()
    main(X, Y)


Fixed submission:
def main():
    X = input()
    Y = input()
    N = len(X)
    M = len(Y)
    dp = [[0]*(M+1) for _ in range(N+1)]
    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            if x == y:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    res = ""
    while N > 0 and M > 0:
        if dp[N][M] == dp[N-1][M]:
            N -= 1
        elif dp[N][M] == dp[N][M-1]:
            M -= 1
        else:
            res = X[N-1] + res
            N -= 1
            M -= 1
    print(res)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main(X, Y):
    M = len(Y)
    dp = [0]*(M+1)
    dp_s = [""]*(M+1)
    for i, x in enumerate(X):
        dp_pre = dp[:]
        dp_s_pre = dp_s[:]
        for j, y in enumerate(Y):
            if x == y:
                dp[j+1] = dp_pre[j] + 1
                dp_s[j+1] = dp_s_pre[j] + x
            elif dp[j+1] < dp[j]:
                dp[j+1] = dp[j]
                dp_s[j+1] = dp_s[j]
    return print(dp_s[M])


if __name__ == "__main__":
    X = input()
    Y = input()
    main(X, Y)


Fixed submission:
def main():
    X = input()
    Y = input()
    N = len(X)
    M = len(Y)
    dp = [[0]*(M+1) for _ in range(N+1)]
    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            if x == y:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    res = ""
    while N > 0 and M > 0:
        if dp[N][M] == dp[N-1][M]:
            N -= 1
        elif dp[N][M] == dp[N][M-1]:
            M -= 1
        else:
            res = X[N-1] + res
            N -= 1
            M -= 1
    print(res)


if __name__ == "__main__":
    main()