Given two character sequences, str_a and str_b, the objective is to determine the maximum length of a subsequence that appears in both strings in the same relative order, though not necessarily contiguously. If no shared characters exist, the result defaults to zero. Input constraints typically specify lengths between 1 and 1000, containing only lowercase English letters.

Mathematical Formulation

Let dp[i][j] denote the length of the longest common subsequence between the prefix of str_a up to index i-1 and the prefix of str_b up to index j-1. The state transition follows two primary cases:

• Matching characters: When str_a[i-1] == str_b[j-1], the current character extends a previously found common subsequence: dp[i][j] = dp[i-1][j-1] + 1
• Mismatched characters: When characters differ, the optimal value propagates from either discarding the current character of str_a or str_b: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Base cases are initialized to zero, representing comparisons against empty prefixes. Iteration proceeds row by row, left to right, guaranteeing all prerequisite states are computed before evaluation.

Two-Dimensional Implementation

The standard approach allocates an (m+1) × (n+1) lookup table. Precomputing boundaries simplifies edge-case handling during iteration and eliminates explicit boundary checks.

class Solution:
    def longestCommonSubsequence(self, first_seq: str, second_seq: str) -> int:
        m, n = len(first_seq), len(second_seq)
        
        # Initialize memoization matrix with zeros
        memo = [[0] * (n + 1) for _ in range(m + 1)]
        
        for r in range(1, m + 1):
            for c in range(1, n + 1):
                if first_seq[r - 1] == second_seq[c - 1]:
                    memo[r][c] = memo[r - 1][c - 1] + 1
                else:
                    memo[r][c] = max(memo[r - 1][c], memo[r][c - 1])
                    
        return memo[m][n]

Computational complexity scales quadratically as O(m × n), with auxiliary memory consumption also at O(m × n).

Space-Optimized One-Dimensional Variant

Observing that computing values for row i only requires data from the current row and the previous row, the state space can be compressed into a single array. Explicitly tracking the diagonal predecessor prevents dependency collisions during array mutation.

class Solution:
    def longestCommonSubsequence(self, first_seq: str, second_seq: str) -> int:
        n = len(second_seq)
        current_row = [0] * (n + 1)
        
        for char_a in first_seq:
            diag_prev = 0  # Captures memo[i-1][j-1] before overwrite
            for j, char_b in enumerate(second_seq, start=1):
                temp_curr = current_row[j]  # Stores memo[i][j-1]
                
                if char_a == char_b:
                    current_row[j] = diag_prev + 1
                else:
                    current_row[j] = max(current_row[j], current_row[j - 1])
                    
                diag_prev = temp_curr  # Advance diagonal pointer
                
        return current_row[n]

This variant maintains the O(m × n) computational bound while reducing spatial overhead to O(n). The explicit retention of the diagonal value ensures correct state propagation without requiring full matrix allocation.