Longest Common Subsequence

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.

Example 1:
Input: text1 = “abcde”, text2 = “ace”
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.

Example 2:
Input: text1 = “abc”, text2 = “abc”
Output: 3
Explanation: The longest common subsequence is “abc” and its length is 3.

Example 3:
Input: text1 = “abc”, text2 = “def”
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

Approach - Bottom Up 2D

• Check if character matches with both string then 1 + solve for subsequence with add 1 on both sides
• If do not matches then next subsequence from either side

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] d = new int[text1.length() + 1][text2.length() + 1];
        for (int i = text1.length() - 1; i >= 0; i--) {
            for (int j = text2.length() - 1; j >= 0; j--) {
                if (text1.charAt(i) == text2.charAt(j))
                    d[i][j] = 1 + d[i+1][j+1];
                else
                    d[i][j] = Math.max(d[i+1][j],d[i][j+1]);    
            }
        }
        return d[0][0];
    }
}

Approach - 1D

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1.length() < text2.length()) {
            String t = text1;
            text1 = text2;
            text2 = t;
        }
        int[] d = new int[text2.length() + 1];
        for (int i = text1.length() - 1; i >= 0; i--) {
            int p = 0;
            for (int j = text2.length() - 1; j >= 0; j--) {
                int t = d[j];
                if (text1.charAt(i) == text2.charAt(j))
                    d[j] = 1 + p;
                else
                    d[j] = Math.max(d[j],d[j+1]);
                p = t;        
            }
        }
        return d[0];
    }
}