Dynamic Programming on Strings

Mastering dynamic programming (DP) for string problems is a critical skill for technical interviews and real-world applications like text editors, genomic sequence alignment, and data validation. While the concept of breaking problems into overlapping subproblems remains core, strings introduce a structured, two-dimensional approach that, once understood, provides a powerful toolkit for solving a wide array of challenges.

The Core Framework: The Two-Dimensional DP Table

The fundamental insight for most string DP problems is to compare two sequences systematically. We typically define a two-dimensional DP table, often named dp[i][j], where i indexes into the first string and j indexes into the second. The state dp[i][j] stores the optimal answer to the subproblem considering the first i characters of string A and the first j characters of string B.

Filling this table requires a careful definition of what "optimal answer" means for the specific problem—whether it's the length of a common subsequence, the minimum edit cost, or a true/false match status. You build the solution bottom-up, starting with trivial base cases (e.g., comparing an empty string to another string) and using a recurrence relation that defines dp[i][j] in terms of solutions to smaller subproblems (dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). This systematic comparison ensures every possible prefix alignment is considered, making the approach both exhaustive and efficient.

Longest Common Subsequence (LCS)

The Longest Common Subsequence (LCS) problem asks: given two strings, what is the length of the longest sequence of characters that appears in both strings in the same relative order, but not necessarily contiguously? For strings "abcde" and "ace", the LCS is "ace" with length 3.

We define dp[i][j] as the length of the LCS of the prefixes A[0..i-1] and B[0..j-1]. The recurrence relation is logical:

• If the current characters match (A[i-1] == B[j-1]), we can extend the best LCS from the previous prefixes: dp[i][j] = 1 + dp[i-1][j-1].
• If they don't match, we cannot extend equally. The best we can do is carry forward the best result from either ignoring A's current character or ignoring B's: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

The base cases are dp[0][j] = 0 and dp[i][0] = 0, representing comparison with an empty string. The final answer is dp[m][n], where m and n are the lengths of the strings. The time and space complexity of the standard solution is $O(mn)$.

Edit Distance (Levenshtein Distance)

Edit Distance, or Levenshtein Distance, quantifies the minimum number of single-character operations (insertions, deletions, or substitutions) required to transform one string into another. It's vital for spell checkers, DNA sequence alignment, and natural language processing.

Here, dp[i][j] represents the minimum edit distance between the prefixes A[0..i-1] and B[0..j-1]. The recurrence builds on three possible actions to make the prefixes match:

1. Deletion from A: Cost = 1 + dp[i-1][j] (remove A[i-1]).
2. Insertion into A (equivalent to deletion from B): Cost = 1 + dp[i][j-1] (add B[j-1] to A).
3. Substitution/No-op: If A[i-1] == B[j-1], cost = dp[i-1][j-1] (no extra cost). If they differ, cost = 1 + dp[i-1][j-1] (substitute one for the other).

The recurrence is: $$dp[i][j]=min(1+dp[i-1][j],1+dp[i][j-1],dp[i-1][j-1]+(0\text{ if }A[i-1]==B[j-1]\text{ else }1))$$

Base cases are intuitive: transforming to/from an empty string requires as many insertions or deletions as the other string's length (dp[i][0] = i, dp[0][j] = j).

Longest Palindromic Subsequence (LPS)

Finding the Longest Palindromic Subsequence within a single string is a clever application of the LCS pattern. A palindromic subsequence reads the same forwards and backwards. The key insight is that the LPS of a string S is simply the LCS of S and its reverse (S_rev). This reduces the problem to one you already know how to solve.

Alternatively, you can define a DP table where dp[i][j] is the length of the LPS in the substring S[i..j]. The recurrence:

• If S[i] == S[j], we can build a palindrome by taking these two ends plus the best palindrome inside: dp[i][j] = 2 + dp[i+1][j-1] (for i < j).
• If S[i] != S[j], the best palindrome lies in one of the inner substrings: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

You fill this table for increasing lengths of substrings, starting from single characters (dp[i][i] = 1).

Regular Expression and Wildcard Matching

These are classic DP problems that test your ability to model more complex matching rules. In Wildcard Matching, a pattern can include ? (matches any single character) and * (matches any sequence of characters, including empty). We define dp[i][j] as true if the first i characters of the text match the first j characters of the pattern.

The recurrence handles three cases:

1. If pattern[j-1] is a normal character or ?: Match requires text[i-1] == pattern[j-1] (or any for ?) and previous prefixes match: dp[i][j] = dp[i-1][j-1].
2. If pattern[j-1] is *: The star can either match zero characters (dp[i][j-1]) or one or more characters, treated as using the star to match the current text char and keeping the star active (dp[i-1][j]). So, dp[i][j] = dp[i][j-1] || dp[i-1][j].

Regular Expression Matching (with . for any char and * for zero or more of the preceding element) is more nuanced because the * is tied to a preceding character. The state definition is similar, but the recurrence must carefully consider when to "use" or "skip" a char* pair in the pattern, making it a frequent interview challenge for testing DP design skills.

Space Optimization: Reducing O(mn) to O(min(m,n))

The standard 2D table uses $O(mn)$ space. However, notice that to fill row i, you only need row i-1 (and sometimes the current row's previous values). This allows for space optimization using a one-dimensional array of size $O(n)$ (or $O(min(m,n))$ if you always use the shorter string's length for the inner dimension).

Common Pitfalls

1. Incorrect State Definition or Indexing: The most frequent error is misaligning string indices with DP table indices. Be rigorously consistent: does dp[i][j] consider the first i chars (using index i-1) or the chars at positions i and j? Always document your definition and check base cases against it.
2. Overlooking Base Cases: Failing to initialize the "empty string" comparison cases correctly will propagate errors throughout the table. For edit distance, dp[i][0] = i is not optional. Always test your logic with a small case where one string is empty.
3. Misapplying Recurrence Logic: In edit distance, confusing when a substitution costs 0 versus 1 is common. In wildcard matching, the treatment of * for matching zero vs. one-or-more characters must be precise. Walk through a simple example step-by-step to verify your recurrence.
4. Premature Space Optimization: Attempting to implement the optimized space version before fully understanding and debugging the standard 2D table version often leads to subtle bugs. Always get the clear version working first, then derive the optimized version as a systematic transformation.

Summary

• String DP problems are typically solved by filling a two-dimensional DP table where dp[i][j] represents the answer for prefixes of the input strings.
• Longest Common Subsequence (LCS) and Edit Distance are foundational patterns; their recurrence relations form the basis for understanding more complex problems like Longest Palindromic Subsequence (LPS).
• Wildcard and Regular Expression Matching require carefully designed DP states to handle special pattern characters like * and ?.
• Space optimization from $O(mn)$ to $O(min(m,n))$ is often possible by recognizing that only the previous row of the DP table is needed for computation, a key skill for writing efficient code.
• Understanding these patterns provides direct solutions to widespread problems in text processing, bioinformatics, and system design, making them a staple of algorithmic interviews.