String Dynamic Programming Tabulation
Proficient Level

Implement the longestCommonSubsequenceLength method that returns the length of the longest common subsequence of two strings.

The input contains two strings, first and second. Your task is to return the length of their longest common subsequence.

A common subsequence is a sequence of characters that appears in both strings in the same order, but the characters do not need to be continuous. For example, for abcde and ace, the longest common subsequence is ace, so the answer is 3.

Example 1
Input:
first (string) = abcde
second (string) = ace
Return:
(int) 3
Example 2
Input:
first (string) = abc
second (string) = abc
Return:
(int) 3
Example 3
Input:
first (string) = abc
second (string) = def
Return:
(int) 0

Use a two-dimensional dynamic programming table.

Let dp[i][j] store the longest common subsequence length using the first i characters of the first string and the first j characters of the second string.

If the current characters match, add 1 to the answer from the previous diagonal cell. If they do not match, take the better answer from removing one character from either string.

Pseudocode:

function longestCommonSubsequenceLength(first, second):
    n = length(first)
    m = length(second)
    dp = 2D array of size (n + 1) x (m + 1) filled with 0
    for i from 1 to n:
        for j from 1 to m:
            if first[i - 1] == second[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]
Run your code to see the result.