Longest Common Subsequence in Every Language

Published on 01 November 2018 (Updated: 02 November 2018)

Longest Common Subsequence in Every Language

Given two arrays of numbers, find the longest common subsequence. For example, let’s say we have the following pair of arrays:

A = [1, 4, 5, 3, 15, 6]
B = [1, 7, 4, 5, 11, 6]

The longest common subsequence is 1, 4, 5, 6.

Requirements

Write a program which accepts two command line arguments–each list–and outputs the longest common subsequence between the two lists. Input arguments should be in comma separated list notation: 1, 2, 14, 11, 31, 7, 9.

Your program should be able to parse these lists into some internal representation in your choice language (ideally an array). From there, the program should compare the two arrays to find the longest common subsequence and output it in comma separated list notation to the user.

The following is recursive pseudocode that you can use for reference:

LCS(arrayA, arrayB, indexA, indexB):
  if indexA == 0 || indexB == 0:
    return 0
  else if arrayA[indexA - 1] == arrayB[indexB - 1]:
    return 1 + LCS(arrayA, arrayB, indexA - 1, indexB - 1)
  else:
    return max(LCS(arrayA, arrayB, indexA - 1, indexB), LCS(arrayA, arrayB, indexA, indexB - 1))

Unfortunately, this pseudocode only gives us the length of the longest common subsequence. Since we want to actually print the result, we’ll probably need to augment this algorithm a bit. Also, it may be useful to implement the memoized solution for the sake of efficiency.

Testing

Verify that the actual output matches the expected output. See the requirements section for an example of the expected output.

Articles

Currently, there are no articles. If you’d like to begin contributing, head over to the repo to get started.

Further Reading