String Dynamic Programming

1. Introduction: The DNA Comparators

In bioinformatics, scientists constantly need to compare DNA sequences. Given two massive strings of genetic code, how similar are they? Where did a mutation (an insertion, deletion, or replacement) occur? We cannot use simple string equality checks (==). We need algorithms that can mathematically quantify the similarity between two sequences, accounting for missing or extra characters.

This is the domain of String Dynamic Programming. String DP algorithms (like Longest Common Subsequence and Edit Distance) form the backbone of diff tools (like git diff), spell checkers, search engine autocorrects, and genetic sequencing software.

String DP is almost exclusively 2D Dynamic Programming, where the state is defined by comparing an index i in String A against an index j in String B.

2. Core Concept: The 2D State and Prefix Comparisons

In String DP, we usually ask questions about the prefixes of the strings. Let dp[i][j] represent the answer for comparing the first i characters of String 1 against the first j characters of String 2.

The Golden Rule of String DP Transitions: At any point (i, j), we look at the characters s1.charAt(i-1) and s2.charAt(j-1):

1. If the characters MATCH: We usually inherit the answer from the previous state without penalty. dp[i][j] = dp[i-1][j-1] + (something).
2. If the characters DO NOT MATCH: We must make a decision. Do we ignore a character from String 1? Or String 2? Or do we substitute it? We look at dp[i-1][j], dp[i][j-1], and dp[i-1][j-1] to make the optimal choice.

3. Beginner Code Example: Longest Common Subsequence (LCS)

Problem Statement: (LeetCode 1143) Given two strings, return the length of their longest common subsequence.

(We covered this in the 2D DP section, but it is the prerequisite for all String DP, so we quickly review the core transition).

public class LCS {
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1]; // +1 for empty string base cases
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // Match! Inherit diagonal and add 1
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    // Mismatch! Take the max of skipping a char in text1 OR text2
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

4. Intermediate Code Example: Edit Distance (Levenshtein Distance)

Problem Statement: (LeetCode 72) Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. Replace a character

The Insight: Let dp[i][j] be the minimum operations to convert word1[0...i] to word2[0...j].

• If characters match: No operation needed! dp[i][j] = dp[i-1][j-1].
• If characters mismatch, we can do one of three things:
  1. Replace: Change word1[i] to word2[j]. Cost is 1 + dp[i-1][j-1] (diagonal).
  2. Delete: Remove word1[i]. Cost is 1 + dp[i-1][j] (top).
  3. Insert: Insert word2[j] into word1. Cost is 1 + dp[i][j-1] (left). We want the minimum of these three choices!

public class EditDistance {
    public static int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        
        // Base Case 1: word1 is empty, we must INSERT all j characters of word2
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        
        // Base Case 2: word2 is empty, we must DELETE all i characters of word1
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1]; // Match, no cost
                } else {
                    // Mismatch, pick cheapest operation
                    int replace = dp[i - 1][j - 1];
                    int delete = dp[i - 1][j];
                    int insert = dp[i][j - 1];
                    
                    dp[i][j] = 1 + Math.min(replace, Math.min(delete, insert));
                }
            }
        }
        
        return dp[m][n];
    }
}

Complexity Analysis:

• Time Complexity: $O(M \times N)$.
• Space Complexity: $O(M \times N)$ for the DP table. (Can be optimized to $O(N)$ by keeping only two rows).

5. Advanced Code Example: Wildcard Matching

Problem Statement: (LeetCode 44) Given an input string s and a pattern p, implement wildcard pattern matching with support for ? and *.

• ? Matches any single character.
• * Matches any sequence of characters (including the empty sequence).

The Insight: The * character breaks standard logic because it can match zero characters OR many characters.

• If p[j] is *, we can choose to:
  1. Have the * match zero characters (meaning we completely ignore the *). State: dp[i][j-1].
  2. Have the * match the current character s[i] and keep going (meaning we might use the * again for the next character). State: dp[i-1][j].

public class WildcardMatching {
    public static boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        
        // Base Case: Empty string matches empty pattern
        dp[0][0] = true;
        
        // Base Case: Empty string matching with pattern containing '*'
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1]; // * can match empty sequence
            }
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char sChar = s.charAt(i - 1);
                char pChar = p.charAt(j - 1);
                
                if (pChar == '?' || sChar == pChar) {
                    // Direct match or '?' match. Inherit diagonal.
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pChar == '*') {
                    // Match zero chars (ignore *) OR Match 1+ chars (consume sChar but keep *)
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else {
                    dp[i][j] = false;
                }
            }
        }
        
        return dp[m][n];
    }
}

Complexity Analysis:

• Time Complexity: $O(M \times N)$.
• Space Complexity: $O(M \times N)$.

6. Common Mistakes Beginners Make

1. Incorrect Base Cases for Empty Strings

   • The Mistake: Initializing dp[0][0] = 0 or false without fully reading the problem context.
   • Why it's wrong: In Edit Distance, converting an empty string to an empty string takes 0 operations, but converting an empty string to "abc" takes 3 operations. In Wildcard Matching, an empty string matches "", but it also matches "***". You MUST pre-fill the 0th row and 0th column based on these rules before the main loop.

2. Using .charAt(i) instead of .charAt(i-1)

   • The Mistake: Because we pad the DP table with a 0 row/col, dp array indices are 1-based, but String indices are 0-based!
   • The Fix: Always use i-1 and j-1 when accessing the string characters inside the dp[i][j] loop.

3. Confusing Wildcard Matching with Regular Expression Matching

   • The Mistake: Trying to use Wildcard logic for Regex (LeetCode 10).
   • Why it's wrong: In Wildcards, * means "any sequence of characters". In Regex, * means "zero or more of the PRECEDING element". The state transitions for Regex are significantly more complex and require looking back two steps (dp[i][j-2]).

7. Interview Q&A

Q1: How do you optimize the space of Edit Distance to $O(N)$? Answer: Notice that dp[i][j] only looks at dp[i-1][j] (directly above), dp[i-1][j-1] (top-left diagonal), and dp[i][j-1] (left). It never looks at row i-2. Therefore, we only need to store int[] prevRow and int[] currRow. We swap them at the end of every i iteration.

Q2: What is the Longest Palindromic Subsequence (LeetCode 516)? Is it the same as LCS? Answer: Yes! A brilliant trick: to find the longest palindromic subsequence of string s, you simply reverse s to create revS. Then, you return the Longest Common Subsequence (LCS) between s and revS! It perfectly maps the problem to standard String DP.

Q3: Can these algorithms be used to find substring matches? Answer: Generally, no. DP finds subsequences (where characters don't have to be contiguous). If you need exact contiguous substring matching, you should use algorithms like KMP (Knuth-Morris-Pratt) or Rabin-Karp, which run in $O(N+M)$ instead of $O(N \times M)$.

8. Practice Problems

1. Delete Operation for Two Strings (LeetCode 583)
   • Hint: Exactly like LCS, but you return (m - LCS) + (n - LCS) to represent the deleted characters.
2. Edit Distance (LeetCode 72)
   • Goal: Master the 3-choice transition.
3. Regular Expression Matching (LeetCode 10)
   • Hint: The hardest String DP problem. Remember that * can cancel out the character before it (e.g., a* can be zero as).

9. Summary

• String DP = 2D Matrices: Rows represent String 1, Columns represent String 2.
• The Padding Rule: Always initialize DP tables to (M+1) x (N+1) to represent the "empty string" base cases safely.
• The Core Transition:
  • Match: Inherit diagonal dp[i-1][j-1].
  • Mismatch: Branch out. Max/Min of Top (dp[i-1][j]), Left (dp[i][j-1]), or Diagonal.
• Wildcards: * characters require OR logic branching to either consume the character or ignore the star.