In this article, we will learn to resolve the Longest Common Subsequence problem by using a dynamic programming algorithm

Problem

  • Given two strings, S of length m and T of length n

  • Write an algorithm to find the length of the longest common subsequence (LCS) of both S and T

Example 1

  • Input: given two strings "ABCD" and "ACBAD"

  • Expected output: 3

  • Explanation: Both the given strings have 2 longest common subsequences: ABD and ACD

Example 2

  • Input: given two strings "XMJYAUZ" and "MZJAWXU"

  • Expected output: 4

  • Explanation: Both the given strings have 1 longest common subsequence: MJAU

Approach: Bottom-Up Dynamic Programming

Consider the two given string S = "ABCD" and T = "ACBAD", say L(i, j) with i and j starting from 1 is the length of the LCS of S and T until i-1 and j-1 characters

  • With i = 1 and j run from 1 to 5: L(i, j) = 1, S(i-1) and T(j-1) has 1 common subsequence 'A'
i = 1, j = 1 -> 5  
  A C B A D
A 1 1 1 1 1  
B  
C  
D
  • With i = 2 and j run from 1 to 5: L(i, j) = 2, S(i-1) and T(j-1) has 1 common subsequence 'AB'
i = 2, j = 1 -> 5  
  A C B A D
A 1 1 1 1 1  
B 1 1 2 2 2  
C  
D
  • With i = 3 and j run from 1 to 5: L(i, j) = 2, S(i-1) and T(j-1) has 2 common subsequences 'AB' and 'AC'
i = 3, j = 1 -> 5  
  A C B A D
A 1 1 1 1 1  
B 1 1 2 2 2  
C 1 2 2 2 2  
D
  • With i = 4 and j run from 1 to 5: L(i, j) = 3, S(i-1) and T(j-1) has 2 length-3 common subsequences 'ABD' and 'ACD', 5 length-2 common subsequences 'AB', 'AC', 'AD', 'BD', and 'CD'
i = 4, j = 1 -> 5  
  A C B A D
A 1 1 1 1 1  
B 1 1 2 2 2  
C 1 2 2 2 2  
D 1 2 2 2 3

From the above solutions break down, at every step we have 2 choices

  • If S(i-1) = T(j-1), L(i, j) = L(i-1, j-1) + 1

  • Else, L(i, j) = max between L(i-1, j) and L(i, j-1)

public class DP_LongestCommonSubsequence {  
    static int lengthOfLongestCommonSubsequence(String S, String T) {
        int m = S.length();
        int n = T.length();
        int[][] lengths = new int[m+1][n+1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if(S.charAt(i-1) == T.charAt(j-1)) {
                    lengths[i][j] = lengths[i-1][j-1] + 1;
                } else {
                    lengths[i][j] = Math.max(lengths[i-1][j], lengths[i][j-1]);
                }
            }
        }

        return lengths[m][n];
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestCommonSubsequence("ABCD", "ACBAD"));
        System.out.println(lengthOfLongestCommonSubsequence("XMJYAUZ", "MZJAWXU"));  
    }
}
  • Output
3  
4
  • Time complexity is O(mn) and space complexity is O(mn) where m and n are the numbers of elements in the two given sequences
Algorithm