Longest Common Subsequence (Problem & Solution)

Longest Common Subsequence (With Solutions in Python, Java & JavaScript)

What is the Longest Common Subsequence Problem?

The Longest Common Subsequence (LCS) problem is a common technical interview question where you're asked to find the longest sequence of characters present in two strings. Variations of this problem are commonly found in real-world applications such as bioinformatics, natural language processing, and text comparison. This problem can be solved using dynamic programming techniques, which involve breaking down the problem into smaller subproblems and then solving them iteratively.

Examples of the Longest Common Subsequence Problem

Given two strings, return the longest common subsequence between the two strings. A subsequence of a string is a string that contains characters from the original string in the same order as the original, but may have characters deleted.

Example 1

Input: s1 = "abccba", s2 = "abddba"
Output: "abba"

Example 2

Input: s1 = "zfadeg", s2 = "cdfsdg"
Output: "fdg"

Example 3

Input: s1 = "abd", s2 = "badc"
Output: "ad" (or "bd")

Constraints

1 <= s1.length, s2.length <= 1000
There may be multiple valid answers, but they'll all have the same length.

How to Solve the Longest Common Subsequence Problem

To solve the longest common subsequence problem (also known as longest common substring), it is helpful to first consider a couple of important properties of the lcs function. Firstly, if two strings s1, s2 end in the same substring then their lcs is the lcs of the two strings without their common substring concatenated with said substring. For example, lcs("abccba", "abddba") = lcs("abcc", "abdd") + "ba", since the length of the longest common subsequence between the two input strings is at minimum the length of the common consecutive string they share.

Secondly, if two strings do not have a common ending substring, the lcs of the two strings will be the same as the lcs resulting from removing the ending of one of the strings. Put another way, lcs(s1, s2) is one of two recursive possibilities:

lcs(s1[:-1], s2)
lcs(s1, s2[:-1])

Recursive Approach

Leveraging the above two properties, we can use a recursive solution to approach a longest common subsequence algorithm and solve this using backtracking.

Starting at the end of the two strings:

If the characters at the end are the same, we can return lcs(s1[:-1], s2[:-1]) + s1[-1].
If the characters are not the same, we must compute both lcs(s1[:-1], s2) and lcs(s1, s2[:-1]), and return the longer given sequence.

Python Code

def solution(s1, s2):
    if len(s1) == 0 or len(s2) == 0:
        return ''
    elif s1[-1] == s2[-1]:
        return solution(s1[:-1], s2[:-1]) + s1[-1]
    else:
        sub1 = solution(s1[:-1], s2)
        sub2 = solution(s1, s2[:-1])
        return sub1 if len(sub1) > len(sub2) else sub2

Time/Space Complexity

Let m and n be the length of the two strings.

Time Complexity: O(2^m * 2^n) in the worst case. This algorithm computes all possible subsequences for both strings, resulting in time complexity of 2^(len(s)) for a string, but it also computes all possible subsequences per subsequence of the other string, hence the product.
Space Complexity: O(max(m,n)). The space complexity is due to the height of the recursion call stack being the maximum length between the two strings.

Recursive Solution With Memoization

When implementing a recursive algorithm, one optimization to always look out for is to address repeated work. By storing the lcs computations in a lookup table, otherwise known as memoization.

Python Code

def solution(s1, s2):
    return solution_recur(s1, s2, {})
def solution_recur(s1, s2, solutions):
    inputs = frozenset([s1, s2])
    solved = solutions.get(inputs, None)
    if solved is not None:
        return solved
    if len(s1) == 0 or len(s2) == 0:
        solved = ''
    elif s1[-1] == s2[-1]:
        solved = solution_recur(s1[:-1], s2[:-1], solutions) + s1[-1]
    else:
        sub1 = solution_recur(s1[:-1], s2, solutions)
        sub2 = solution_recur(s1, s2[:-1], solutions)
        solved = sub1 if len(sub1) > len(sub2) else sub2
    solutions[inputs] = solved
    return solved

Dynamic Programming Approach

To solve this using a dynamic programming approach, this solution will construct a table of results, and then trace back through the table from the bottom up to construct the longest subsequence.

Python Code

class SolutionNode:
    def __init__(self, direction="sink", value=0):
        self.direction = direction
        self.value = value

def solution(s1, s2):
    if len(s1) == 0 or len(s2) == 0:
        return ''
    lcs = [[SolutionNode() for x in range(len(s2)+1)]
           for y in range(len(s1)+1)]
    for i, row in enumerate(lcs[1:], 1):
        for j, cell in enumerate(row[1:], 1):
            if s1[i-1] == s2[j-1]:
                cell.value = lcs[i-1][j-1].value + 1
                cell.direction = 'up-left'
            elif lcs[i][j-1].value == lcs[i-1][j].value:
                cell.direction = 'both'
                cell.value = lcs[i][j-1].value
            elif lcs[i][j-1].value > lcs[i-1][j].value:
                cell.direction = 'left'
                cell.value = lcs[i][j-1].value
            else:
                cell.direction = 'up'
                cell.value = lcs[i-1][j].value
    i = len(s1)
    j = len(s2)
    node = lcs[i][j]
    val = node.value
    result = ''
    while val > 0:
        if node.direction == 'up' or node.direction == 'both':
            i -= 1
        elif node.direction == 'left':
            j -= 1
        else:
            i -= 1
            j -= 1
            result = s1[i] + result
        node = lcs[i][j]
        val = node.value
    return result

Additional Reading

The final solution can be further improved. One such way is the Hunt-Szymanski Algorithm.

Longest Common Subsequence Frequently Asked Questions (FAQ)

Which approach to solving the longest common subsequence is the most efficient?

The optimal time complexity of the longest common subsequence (LCS) algorithm is O(m * n), where mand n are the lengths of the input strings. This is typically implemented using dynamic programming, where we create a matrix of size (m+1) x (n+1) to store the prefix lengths and fill the matrix iteratively, requiring examining each cell, which takes constant time. Another way to achieve this time complexity is using recursion with memoization, ensuring no duplicate computations are made when visiting each node in the recursive tree.

Can there be more than one longest common subsequence?

No, by definition, there can only be one longest common subsequence (LCS) between two strings, defined by the longest subsequence that is common to both strings, appearing in the same order.