Array String Dynamic Programming Memoization Tabulation
Proficient Level

Implement the longestCommonSubsequenceDpLength method that returns the LCS length using dynamic programming.

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

A subsequence keeps characters in the same relative order but does not need to use consecutive characters. The same subsequence must appear in both strings.

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 dynamic programming to compare prefixes of both strings.

Let dp[i][j] represent the LCS length using the first i characters of first and the first j characters of second.

If the current characters match, extend the previous diagonal answer by one. If they do not match, take the better result from skipping one character from either string.

Pseudocode:

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