String DP is a common DP category in coding interviews. It covers problems where the input involves one or two strings and the goal is to find some optimal property: the longest common subsequence, the minimum edit distance, whether one string matches a pattern, and so on.

What Is String DP?

The defining characteristic is how we define subproblems. When we have two strings, we typically build a 2D DP table where dp[i][j] represents the answer for the first i characters of string1 and the first j characters of string2. When we have one string, the table might be 1D (processing character by character) or 2D (considering substrings from index i to index j).

This is different from, say, knapsack problems where one dimension is the item index and the other is a capacity. In string DP, both dimensions correspond to positions within strings, and the transitions depend on whether characters at those positions match.

How to Identify String DP Problems

Not every problem involving strings requires DP. String DP problems have specific signals:

Strong signals:

The problem involves comparing two strings (LCS, edit distance, interleaving)
You need to find the longest or shortest subsequence with some property
The problem asks about edit operations (insert, delete, replace)
Pattern matching with wildcards or regex
The problem says "subsequence" rather than "substring" (subsequences often need DP, while substrings sometimes have sliding window solutions)

Common problem types:

Category	Examples	State Definition
Two-string comparison	LCS, Edit Distance, Interleaving String	`dp[i][j]` = answer for prefixes of length i and j
Palindrome problems	Longest Palindromic Subsequence, Palindrome Partitioning	`dp[i][j]` = answer for substring from i to j
String matching	Wildcard Matching, Regular Expression Matching	`dp[i][j]` = does pattern[:i] match text[:j]
Single-string decomposition	Word Break, Decode Ways	`dp[i]` = answer for prefix of length i

The first three categories use 2D tables. The last one uses a 1D table because we only process one string from left to right.

The Core Idea

The template for two-string DP:

State Definition

Given two strings s1 of length m and s2 of length n, define:

dp[i][j] = the answer considering the first i characters of s1 and the first j characters of s2

The table has dimensions (m+1) x (n+1). The extra row and column at index 0 represent the empty string prefix.

Base Cases

The base cases handle what happens when one or both strings are empty:

dp[0][0] = answer when both strings are empty
dp[i][0] = answer when s2 is empty (only s1's first i characters)
dp[0][j] = answer when s1 is empty (only s2's first j characters)

The exact values depend on the problem. For LCS, all base cases are 0 (an empty string has no common subsequence with anything). For edit distance, dp[i][0] = i (deleting all i characters) and dp[0][j] = j (inserting all j characters).

The Match/Mismatch Branch

At each cell dp[i][j], we look at the current characters s1[i-1] and s2[j-1] (using 0-indexed strings but 1-indexed DP table) and branch:

If characters match (s1[i-1] == s2[j-1]): We can use this match. The answer typically comes from the diagonal cell dp[i-1][j-1], possibly with some addition.

If characters do not match: We consider multiple options, usually involving dp[i-1][j], dp[i][j-1], and sometimes dp[i-1][j-1], taking the best one according to the problem's objective.

The 2D Table Structure

We fill the table row by row, left to right. Each cell depends only on the cell above it, the cell to its left, and the cell diagonally above-left.

This dependency pattern means we can optimize space from O(m * n) to O(min(m, n)) by keeping only the previous row. The full 2D table is clearer to debug; the rolling array is an optimization on top.

Single-String DP

When the problem involves only one string, there are two common patterns:

Left-to-right 1D DP: dp[i] = answer for the prefix of length i. Used in Word Break and Decode Ways. Each cell looks back at earlier cells.
Gap-based 2D DP: dp[i][j] = answer for the substring from index i to index j. Used in Longest Palindromic Subsequence and Palindrome Partitioning. The table is filled by increasing gap size (length of substring).

Example Walkthrough: Edit Distance (LeetCode 72)

Problem Statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2. You have three operations:

Insert a character
Delete a character
Replace a character

This is also known as the Levenshtein distance, and it is a foundational string DP problem.

Intuition

Define dp[i][j] as the minimum edit distance between the first i characters of word1 and the first j characters of word2. The three operations map to movements in the DP table.

If word1[i-1] and word2[j-1] match, no operation is needed and we carry forward dp[i-1][j-1]. If they do not match, we have three choices and take the minimum:

Replace word1[i-1] with word2[j-1]: costs 1 operation plus dp[i-1][j-1] (we fixed the mismatch at both positions, move diagonally)
Delete word1[i-1]: costs 1 operation plus dp[i-1][j] (we removed a character from word1, move up)
Insert word2[j-1] into word1: costs 1 operation plus dp[i][j-1] (we matched word2's character by inserting, move left)

The base cases: converting an empty string to a string of length j requires j insertions. Converting a string of length i to an empty string requires i deletions.

Step-by-Step Trace

Trace word1 = "horse" and word2 = "ros".

First, set up the base cases. The first row represents converting an empty string to "ros" (0, 1, 2, 3 insertions). The first column represents converting "horse" to an empty string (0, 1, 2, 3, 4, 5 deletions).

Trace a few key cells:

dp[1][1] (h vs r): Characters do not match. Replace = dp[0][0] + 1 = 1. Delete = dp[0][1] + 1 = 2. Insert = dp[1][0] + 1 = 2. Minimum = 1.

dp[2][2] (o vs o): Characters match. dp[1][1] = 1. No extra cost. Result = 1.

dp[3][1] (r vs r): Characters match. dp[2][0] = 2. No extra cost. Result = 2.

dp[5][3] (e vs s): Characters do not match. Replace = dp[4][2] + 1 = 4. Delete = dp[4][3] + 1 = 3. Insert = dp[5][2] + 1 = 5. Minimum = 3.

The answer is dp[5][3] = 3. One optimal sequence: replace "h" with "r", delete "r", delete "e". This transforms "horse" to "rorse" to "rose" to "ros".

Implementation

Complexity Analysis

Time Complexity: O(m * n), where m and n are the lengths of the two strings. We fill every cell in the table exactly once.
Space Complexity: O(m * n) for the DP table. This can be optimized to O(min(m, n)) by keeping only the previous row, since each cell depends only on the current and previous rows.

Quiz

Introduction Quiz

10 quizzes

Introduction to String DP