Counting maximum number of elements in right order

Question

There is an source and target.

example:

source:[a,b,e,d,s,t,c,v,t]

target:[a,e,v,g,r,b,c,v,t]

target and source have same number of elements.

how can I count elements in source ordered correctly according to target?

so, target means that elements in source should be ordered in target's order.

and count maximum number of properly ordered elements in source.

so the answer for example is 5 (a,b,c,v,t).

of course there are two elements in order like (a,e),(a,b) but out put should be maximum elements.

how can I do it neat and compactly?

My code

I used combinations, counting from max element number to 0.

n=len(target)
k=1
for check in range(n,-1,-1):
            while k!=0:
                for j in combinations(souce,check):
                    if j in combinations(target,check):
                        answer_co.append(check)
                        k=0
                        break

Answer 1

This is a classical LCS problem, which can be solved in DP as suggested by earlier post. Time Complexity of the implementation is O(mn) which is much better than the original code implementation. (An exercise for the reader to study. ;-)

The next code fragment assumes that the source/target are both strings.

Here is the DP approach:

class Solution:

def lcs(self, source: str, target: str) -> int:
    n,  m = len(source), len(target)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n):
        for j in range(m):
            if source[i] == target[j]:
                dp[i + 1][j + 1]= dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
    return dp[-1][-1]