Algorithm Approach

Let dp[m][n] denote the length of the longest common subsequence between the first m characters of string str_a and the first n characters of string str_b. By utilizing an extra row and column for empty prefixes, the base cases naturally become dp[0][n] = 0 and dp[m][0] = 0.

The state transitions follow these rules:

• If the current characters match, i.e., str_a[m-1] == str_b[n-1], the subsequence length extends by one: dp[m][n] = dp[m-1][n-1] + 1.
• If the characters differ, the maximum length is inherited from either excluding the current character of str_a or str_b: dp[m][n] = max(dp[m-1][n], dp[m][n-1]).

Implementation

Python

class Solution:
    def computeLcs(self, str_a: str, str_b: str) -> int:
        size_a, size_b = len(str_a), len(str_b)
        dp = [[0] * (size_b + 1) for _ in range(size_a + 1)]

        for m in range(1, size_a + 1):
            for n in range(1, size_b + 1):
                if str_a[m - 1] == str_b[n - 1]:
                    dp[m][n] = dp[m - 1][n - 1] + 1
                else:
                    dp[m][n] = max(dp[m - 1][n], dp[m][n - 1])

        return dp[size_a][size_b]

C++

class Solution {
public:
    int computeLcs(std::string str_a, std::string str_b) {
        int size_a = str_a.length();
        int size_b = str_b.length();
        std::vector<std::vector<int>> dp(size_a + 1, std::vector<int>(size_b + 1, 0));

        for (int m = 1; m <= size_a; ++m) {
            for (int n = 1; n <= size_b; ++n) {
                if (str_a[m - 1] == str_b[n - 1]) {
                    dp[m][n] = dp[m - 1][n - 1] + 1;
                } else {
                    dp[m][n] = std::max(dp[m - 1][n], dp[m][n - 1]);
                }
            }
        }
        return dp[size_a][size_b];
    }
};