1143. Longest Common Subsequence

Hello, reader 👋🏽 ! Welcome to day 75 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 1143. Longest Common Subsequence.

🤔 Problem Statement

Given two strings text1 and text2, return the length of their longest common subsequence*. If there is no *common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
- For example, "ace" is a subsequence of "abcde".

A **common subsequence** of two strings is a subsequence that is common to both strings.

E.g.:
- text1 = "abcde", text2 = "ace" => 3
- text1 = "abc", text2 = "abc" => 3

💬 Thought Process - Memoization

The naive way of solving this problem would be to generate all possible subsequences for both the strings and find the longest common ones among them.
But to find all the subsequences it would take O(2^n + 2^m). And this is not efficient.
Plus there might be characters in both the strings that don't match at all. And finding all the subsequences with differences is extra work.
To solve the problem, we would try to generate only the valid subsequences such that characters in both the strings match.
Hence we would simultaneously recurse over both strings with two pointers: i and j, with i representing indices for text and j representing indices for text2.
There could be two cases:
- Characters at text1[i] and text2[j] don't match:
  - Maybe there's a future character in text1 that matches with the current character in text2 => update the pointer for string text1, i.e. i.
  - Maybe there's a future character in text2 that matches with the current character in text1 => update the pointer for string text2, i.e. j.
Characters at text1[i] and text2[j] match:
- We update both the pointers i and j and search recursively for remaining string. We also return 1 indicating that there was string of length 1 that matched.
Since we could be solving problems multiple times for the same pairs of i and j, we can cache these results that would represent the length of string matched until indices i and i.

👩🏽‍💻 Solution - Memoization

Below is the code for the approach for solving this problem using memoization.

class Solution {
    private int[][] memo;
    private int m, n;
    public int longestCommonSubsequence(String text1, String text2) {
        m = text1.length();
        n = text2.length();

        memo = new int[m][n];
        for(int[] row: memo) {
            Arrays.fill(row, -1);
        }

        return lcsHelper(text1, m-1, text2, n-1);
    }

    private int lcsHelper(String text1, int i, String text2, int j) {
        if(i < 0 || j < 0) return 0;

        if(memo[i][j] != -1) return memo[i][j];

        char text1Ch = text1.charAt(i);
        char text2Ch = text2.charAt(j);

        if(text1Ch == text2Ch) {
            return memo[i][j] = 1 + lcsHelper(text1, i-1, text2, j-1);
        }

        int decrementI = lcsHelper(text1, i-1, text2, j);
        int decrementJ = lcsHelper(text1, i, text2, j-1);

        return memo[i][j] = Math.max(decrementI, decrementJ);
    }
}

Time Complexity: O(m * n)
    - m = length of text1
    - n = length of text2
Space Complexity: O(m * n)
    - m = length of text1
    - n = length of text2

💬 Thought Process - Tabulation

We can also solve this problem using DP bottom-up/ tabulation where we will solve for the longest common substring from the first character for both the strings.
We will use a 2D array to tabulates the values calculated for previous pair of indices and then use it for the current pair.
- We'll work our way from first to the last indices of the strings.
One change we will make while tabulating is that our i and j indices would represent the number of common substrings when i characters are chosen from text1 and j characters are chosen from text2.

👩🏽‍💻 Solution - Tabulation

Below is the code for the approach for solving this problem using tabulation.

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        if(text1 == null || text1.length() == 0 
           || text2 == null || text2.length() == 0) {
            return 0;
        }

        int n = text1.length();
        int m = text2.length();
        int[][] dp = new int[n+1][m+1];

        for(int i = 0; i<m; i++) {
            dp[0][i] = 0;
        }
        for(int j = 0; j<n; j++) {
            dp[j][0] = 0;
        }

        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=m; j++) {
                char f = text1.charAt(i-1);
                char s = text2.charAt(j-1);

                if(f == s) {
                    dp[i][j] = 1 + dp[i-1][j-1];
                }
                else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        return dp[n][m];
    }
}

Time Complexity: O(m * n)
    - m = length of text1
    - n = length of text2
Space Complexity: O(m * n)
    - m = length of text1
    - n = length of text2

You can find the link to the GitHub repo for this question here: 1143. Longest Common Subsequence.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!