DSAHardDynamic Programming
Longest Common Subsequence
đ Problem
Given two strings, find the length of their longest common subsequence â a sequence of characters that appears in both strings in the same relative order (not necessarily contiguous).
đ§ Approach
Build a 2D table dp[i][j] representing the LCS length using the first i characters of string A and first j characters of string B. If the characters match, dp[i][j] = dp[i-1][j-1] + 1. If they don't match, take the best of ignoring one character from either string: max(dp[i-1][j], dp[i][j-1]).