Longest Common Subsequence (LCS) Editorial

Practice Problem Link: Practice Problem | Longest Common Subsequence

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given two strings s1 and s2, find the length of their longest common subsequence. If there is no common subsequence, return 0.

Naive Approach

We can solve this problem by a brute force recursion.

• Let’s think about the base cases first. When either of the strings are empty, the LCS is 0.
• Else, if the current character of the strings match, we check for the previous prefix of the whole string, and add 1 to the answer.
• If, the characters don't match, we take the maximum of LCS(string1_length - 1, string2_length) and LCS(string1_length, string2_length - 1).

Analysis

• Time Complexity: Exponential
• Space Complexity: Exponential due to memory allocated in recursion stack.

Implementation

C++

int getLCS(string s1, string s2, int n, int m) {
   if(n == 0 || m == 0) {
       return 0;
   }
   if(s1[n - 1] == s2[m - 1]) {
       return getLCS(s1, s2, n - 1, m - 1) + 1;
   } else {
       return max(getLCS(s1, s2, n - 1, m), getLCS(s1, s2, n, m - 1));
   }
}
int getLengthOfLCS(string s1, string s2) {
   int n = s1.length();
   int m = s2.length();
   return getLCS(s1, s2, n, m);
}

Java

class Solution {
   int getLCS(String s1, String s2, int n, int m) {
       if(n == 0 || m == 0) {
           return 0;
       }
       if(s1.charAt(n - 1) == s2.charAt(m - 1)) {
           return getLCS(s1, s2, n - 1, m - 1) + 1;
       } else {
           return Math.max(getLCS(s1, s2, n - 1, m), getLCS(s1, s2, n, m - 1));
       }
   }
   int getLengthOfLCS(String s1, String s2) {
       int n = s1.length();
       int m = s2.length();
       return getLCS(s1, s2, n, m);
   }
}

Optimal Approach

Observe here that when we call the function getLCS(), it recursively calls itself with the same parameters multiple times. So if we can precompute those values once they are encountered, we wont have to recursively search for those results again.

We can solve this by using Dynamic Programming, and memoizing the results into an DP array, where DP[i][j] represents the length of the Longest Common Subsequence of the Strings from [0, i - 1] and from [0, j - 1].

Analysis

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

where m and n denotes the lengths of the strings.

Implementation

C++

vector<vector<int>> dp;
int getLCS(string s1, string s2, int n, int m) {
   if(n == 0 || m == 0) {
       return 0;
   }
   if(dp[n][m] != -1) {
       return dp[n][m];
   }
   if(s1[n - 1] == s2[m - 1]) {
       return dp[n][m] = getLCS(s1, s2, n - 1, m - 1) + 1;
   } else {
       return dp[n][m] = max(getLCS(s1, s2, n - 1, m), getLCS(s1, s2, n, m - 1));
   }
}
int getLengthOfLCS(string s1, string s2) {
   int n = s1.length();
   int m = s2.length();
   vector<vector<int>> temp(n + 1, vector<int> (m + 1, -1));
   dp = temp;
   return getLCS(s1, s2, n, m);
}

Java

class Solution {
   int dp[][];
   int getLCS(String s1, String s2, int n, int m) {
       if(n == 0 || m == 0) {
           return 0;
       }
       if(dp[n][m] != -1) {
           return dp[n][m];
       }
       if(s1.charAt(n - 1) == s2.charAt(m - 1)) {
           return dp[n][m] = getLCS(s1, s2, n - 1, m - 1) + 1;
       }
       else {
           return dp[n][m] = Math.max(getLCS(s1, s2, n - 1, m), getLCS(s1, s2, n, m - 1));
       }
   }
   int getLengthOfLCS(String s1, String s2) {
       int n = s1.length();
       int m = s2.length();
       dp = new int[n + 1][m + 1];
       for(int i = 0; i <= n; i++) {
           for(int j = 0; j <= m; j++) {
               dp[i][j] = -1;
           }
       }
       return getLCS(s1, s2, n, m);
   }
}

Implementation (Bottom-up)

C++

int getLengthOfLCS(string s1, string s2) {
   int n = s1.length();
   int m = s2.length();
   vector<vector<int>> dp(n + 1, vector<int>(m + 1));
   for(int i = 0; i <= n; i++) {
       for(int j = 0; j <= m; j++) {
           if(i == 0 || j == 0) {
               dp[i][j] = 0;
           } else {
               if(s1[i - 1] == s2[j - 1]) {
                   dp[i][j] = dp[i - 1][j - 1] + 1;
               } else {
                   dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
               }
           }
       }
   }
   return dp[n][m];
}

Java

class Solution {
   int getLengthOfLCS(String s1, String s2) {
       int n = s1.length();
       int m = s2.length();
       int[][] dp = new int[n + 1][m + 1];
       for(int i = 0; i <= n; i++) {
           for(int j = 0; j <= m; j++) {
               if(i == 0 || j == 0) {
                   dp[i][j] = 0;
               } else {
                   if(s1.charAt(i - 1) == s2.charAt(j - 1)) {
                       dp[i][j] = dp[i - 1][j - 1] + 1;
                   } else {
                       dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                   }
               }
           }
       }
       return dp[n][m];
   }
}