Longest common subsequence

Part 1 - sequence lengths

Given two strings, find the length of the longest subsequence common to both strings. Items in the subsequence do not have to be next to each other.

Input:   s1 = "aabbcc"
         s2 = "axbxcx"
Output:  3
Note:    "abc" is the longest common subsequence

Solution	Time	Space
Brute force	O(2^m n)	O(1)
Dynamic programming	O(mn)	O(mn)

Solution 1.1: Brute force

Consider all possible sequences of one string
For each of these sequences, check if it's a subsequence in the other string
If it is, note its length if it's longer than the last longest subsequence

def longest_common_subsequence(s1, s2)
  m, n = s1.length, s2.length
  longest_length = 0
  (1 .. 2**m-1).each do |bitmask|
    subsequence = []
    i = 0
    while 2**i <= bitmask
      if bitmask & 2**i != 0
        subsequence << s1[i]
      end
      i += 1
    end
    i = 0
    s2.each_char do |c|
      if subsequence[i] == c
        i += 1
      end
    end
    if i == subsequence.length && i > longest_length
      longest_length = i
    end
  end
  longest_length
end

Time	O(n * 2^m)	m comparisons for each of 2ⁿ possible subsequences
Space	O(1)	The length of the longest subsequence seen

Solution 1.2: Dynamic programming

Compare every prefix of one string to the other
If the last characters of each prefix match, add 1 to the longest length without the last characters
Otherwise, the longest length is the last longest length

def longest_common_subsequence(s1, s2)
  m, n = s1.length, s2.length
  lcs_lengths = Array.new(m + 1) { Array.new(n + 1, 0) }
  (1 .. m).each do |i|
    (1 .. n).each do |j|
      if s1[i-1] == s2[j-1]
        lcs_lengths[i][j] = 1 + lcs_lengths[i-1][j-1]
      else
        lcs_lengths[i][j] = [
          lcs_lengths[i-1][j],
          lcs_lengths[i][j-1]
        ].max
      end
    end
  end
  lcs_lengths[m][n]
end

Time	O(mn)	Two loops of m and n time
Space	O(mn)	2D array of longest common subsequence lengths

Part 2 - longest sequences

Find the longest common subsequence common to both strings. If more than one subsequence share the same length, return any of them.

Input:   s1 = "aabbcc"
         s2 = "axbxcx"
Output:  "abc"

Solution	Time	Space
Brute force	O(2^m n)	O(min(m,n))
Dynamic programming 1	O(mn * min(m,n))	O(mn * min(m,n))
Dynamic programming 2	O(mn)	O(mn)

Solution 2.1: Brute force

Similar to solution 1.1, consider all subsequences. However, instead of saving the length of the longest subsequence seen, save the longest sequence itself.

Time	O(n * 2^m)	m comparisons for each of 2ⁿ possible subsequences
Space	O(min(m,n))	Length can't exceed the shorter of the two strings

Solution 2.2: Dynamic programming 1

Similar to solution 2.1, iterate over all prefixes of the two strings. However, instead of saving the length of the longest subsequence seen, save a copy of the longest sequence itself.

Time	O(mn * min(m,n))	Two loops of m and n time with array copying
Space	O(mn * min(m,n))	2D array of longest common subsequences

Solution 2.3: Dynamic programming 2

Calculate the 2D array of longest subsequence lengths, exactly like in solution 2 in part 1. Now that we have the array of lengths, we can traverse the array in O(m + n) time to generate a longest subsequence.

Time	O(mn)	Two loops of m and n time
Space	O(mn)	2D array of longest common subsequence lengths

Level Order