Where am I going wrong in the basic implementation of Longest Common Subsequence

Question

I've tried to implement LCS in python using the following code, where am I going wrong ?

def lcs(s1,s2):
    if len(s1) == 0 or len(s2) == 0:
        return ""
    
    n = len(s1) - 1
    m = len(s2) - 1
        
    if s1[n] == s2[m]:
        return lcs(s1[:n], s2[:m]) + s1[n]
    else:
        return lcs(s1[:n], s2), lcs(s1, s2[:m])

s1 = "abcbac"
s2 = "babacc"
res = lcs(s1, s2)
print(res)

I get cannot concatenate tuple with string error. I tried to resolve it by converting s1[n] into a tuple, that didnt work, I also tried to use a global variable and append s1[n] to it.

How can I change the above code the implement LCS ?

Answer 1

You are returning a tuple in the else case

def lcs(s1,s2):
    if not s1 or not s2:
        return ''
        
    n = len(s1) - 1
    m = len(s2) - 1
        
    if s1[n] == s2[m]:
        return lcs(s1[:n], s2[:m]) + s1[n]
    else:
        return max(lcs(s1[:n], s2), lcs(s1, s2[:m]), key=lambda x: len(x))

The correct way to do this, is to return the longest common subsequence from the two recursions. I'd also note that this recursion based approach is kind of slow.