String DP

Longest Common Subsequence

Compare two strings character by character. If chars match, LCS = 1 + LCS of remaining. If not, take the max of skipping either character. Build a 2D table bottom-up.

O(m*n)

How It Works

The longest common subsequence of two strings is the longest sequence of characters appearing in both, in order but not necessarily contiguously. Define dp[i][j] as the LCS length of the first i characters of one string and the first j of the other. When the current characters match, dp[i][j] = dp[i−1][j−1] + 1; otherwise take the better of skipping a character from either string: max(dp[i−1][j], dp[i][j−1]).

Filling the table takes O(m·n) time, versus the exponential blowup of trying all 2^n subsequences. Since each row depends only on the previous one, space compresses to O(min(m, n)). LCS underlies diff tools and is the template for many two-string DP problems.

Step-by-Step Visualization

LCS of 'abcde' and 'ace'

s1abcde

s2ace

1/2

Code

Java

static int longestCommonSubsequence(String text1, String text2) {
  int m = text1.length(), n = text2.length();
  int[][] dp = new int[m+1][n+1];

  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      dp[i][j] = text1.charAt(i-1) == text2.charAt(j-1)
        ? dp[i-1][j-1] + 1
        : Math.max(dp[i-1][j], dp[i][j-1]);
  return dp[m][n];
}

Tips & Gotchas

1Same as d2-lcs but specifically for string DP problems

2Match: dp[i][j] = dp[i-1][j-1] + 1. Mismatch: max of skip either

3Can reconstruct the subsequence by backtracking

Practice Problems

1Longest Common Subsequence
2Delete Operation for Two Strings
3Uncrossed Lines
4Shortest Common Supersequence

About the String DP Pattern

When string problems involve comparing two strings character by character (subsequences, transformations, matching), dynamic programming builds the solution from smaller substrings up to the full strings.

Key insight

Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).

Common String Interview Problems

Longest Substring Without Repeating Characters
Valid Anagram
Longest Palindromic Substring
Minimum Window Substring
Group Anagrams

Frequently Asked Questions

What is the difference between longest common subsequence and longest common substring?

A subsequence keeps relative order but allows gaps, while a substring must be contiguous. Their DP recurrences differ in the mismatch case: substring DP resets to zero on a mismatch, whereas subsequence DP carries forward the best of the two neighboring cells.

How do I recover the actual subsequence, not just its length?

Trace back from dp[m][n]: on a character match move diagonally and record the character, otherwise step toward whichever neighbor holds the larger value. Note that reconstruction needs the full 2D table, so the O(n) space optimization sacrifices it.