String Dynamic Programming

1. Introduction: The 2D Grid

When you need to compare two strings, the brute force approach is usually $O(2^N)$ because you are generating all possible subsequences or edits. To optimize this, we use a 2D Dynamic Programming matrix. String DP is one of the most recognizable patterns in computer science. If you have a problem involving two strings and need to find the "longest", "shortest", or "minimum edits" between them, you are almost certainly looking at a 2D DP matrix where String A is the rows and String B is the columns.

2. Core Concept: The 2D String DP Template

The matrix dp[i][j] represents the answer to the problem using the first i characters of String A and the first j characters of String B.

The Golden Rules of String DP:

1. If the characters match (A[i-1] == B[j-1]), you usually take the diagonal value (dp[i-1][j-1]) and add 1 (for length) or keep it the same (for cost).
2. If the characters DO NOT match, you usually look at the top (dp[i-1][j]) and the left (dp[i][j-1]) and take the max or min depending on the problem.

(Note: The matrix is sized [N+1][M+1]. The 0 index represents the empty string "". This elegantly handles all edge cases without throwing ArrayOutOfBounds exceptions).

3. Advanced Code Example: Longest Common Subsequence

Problem Statement: (LeetCode 1143) Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence does not have to be contiguous. (e.g., "ace" is a subsequence of "abcde").

The Insight:

• If text1[i] == text2[j], they are part of the LCS! Add 1 to the LCS of the strings before these characters.
• If they don't match, the LCS is the max of either ignoring the character from text1, or ignoring the character from text2.

public class LongestCommonSubsequence {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        // Matrix size is +1 to handle the empty string base cases (which default to 0)
        int[][] dp = new int[m + 1][n + 1];
        
        // Iterate through both strings
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                
                // Characters Match! Take the diagonal (previous state) + 1
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } 
                // Characters Don't Match! Take the max of ignoring row or ignoring col
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
                
            }
        }
        
        return dp[m][n];
    }
}

Complexity Analysis:

• Time Complexity: $O(M \times N)$ to fill the grid.
• Space Complexity: $O(M \times N)$ for the DP table. (Can be optimized to $O(\min(M, N))$ by only keeping the previous row).

4. Advanced Code Example: Edit 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 3 operations: Insert a character, Delete a character, Replace a character.

The Insight:

• If characters match, the cost is 0! Take the diagonal (dp[i-1][j-1]).
• If they don't match, you must do 1 operation. Which one?
  • Delete: dp[i-1][j] + 1 (Look up)
  • Insert: dp[i][j-1] + 1 (Look left)
  • Replace: dp[i-1][j-1] + 1 (Look diagonal) Take the min of all three!

public class EditDistance {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        
        int[][] dp = new int[m + 1][n + 1];
        
        // 1. Initialize Base Cases
        // If word2 is empty, it costs 'i' deletions to convert word1 to word2
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; 
        }
        // If word1 is empty, it costs 'j' insertions to convert word1 to word2
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        
        // 2. Fill the DP Table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // Match! No cost. Inherit from diagonal.
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // Mismatch! Take the min of Insert, Delete, or Replace, plus 1 operation cost.
                    int replace = dp[i - 1][j - 1];
                    int delete = dp[i - 1][j];
                    int insert = dp[i][j - 1];
                    
                    dp[i][j] = Math.min(replace, Math.min(delete, insert)) + 1;
                }
                
            }
        }
        
        return dp[m][n];
    }
}

5. Advanced Code Example: Word Break

Problem Statement: (LeetCode 139) Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

The Insight: This is a 1D String DP problem. We want to know if dp[i] (the string up to index i) can be broken down. It can be broken down IF there is some valid previous cut dp[j], AND the substring from j to i is in the dictionary!

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        
        // Base case: The empty string is always valid
        dp[0] = true;
        
        for (int i = 1; i <= s.length(); i++) {
            // Check all possible previous cuts 'j'
            for (int j = 0; j < i; j++) {
                // If the string up to 'j' was valid, AND the rest of the string is in the dictionary
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // We found a valid cut, no need to check further 'j's for this 'i'
                }
            }
        }
        
        return dp[s.length()];
    }
}

6. Common Mistakes Beginners Make

1. Forgetting the +1 Matrix Size

   • The Mistake: int[][] dp = new int[m][n];
   • Why it's wrong: You need a row/col for the Empty String base case! Without it, you have to write incredibly messy if (i == 0) blocks inside your inner loops. By using m+1, dp[0][0] handles the base cases cleanly.

2. Index Off-by-One in Strings

   • The Mistake: if (word1.charAt(i) == word2.charAt(j))
   • Why it's wrong: If your DP matrix is sized m+1, your i and j loops go from 1 to m. But strings are 0-indexed! You MUST check charAt(i - 1) to get the correct character.

3. Using 2D DP when 1D is enough

   • The Mistake: Allocating a full $O(M \times N)$ matrix.
   • Why it's wrong: If you look at the LCS logic, dp[i][j] only ever looks at the current row (dp[i][j-1]) and the previous row (dp[i-1]...). It never looks at row i-2. Therefore, you only need to store 2 rows in memory at any given time, dropping Space Complexity to $O(N)$.

7. Interview Q&A

Q1: How do you reconstruct the actual Longest Common Subsequence string? Answer: You start at dp[m][n] and walk backward! If text1[i-1] == text2[j-1], that character is part of the LCS. Prepend it to a StringBuilder, and move diagonally up-left (i-1, j-1). If they don't match, look at dp[i-1][j] and dp[i][j-1] and move in the direction of the larger number.

Q2: Can we solve Edit Distance with BFS? Answer: Surprisingly, yes! You can treat every string state as a graph node. The edges are the Insert, Delete, and Replace operations. You do a BFS until you hit the target string. However, since the string length can be 500, the graph explodes to millions of nodes, causing a Memory Limit Exceeded error. DP mathematically condenses it.

8. Practice Problems

1. Longest Common Subsequence (LeetCode 1143)
   • Goal: Memorize the match ? diag+1 : max(top, left) pattern.
2. Edit Distance (LeetCode 72)
   • Goal: Memorize the match ? diag : min(top, left, diag) + 1 pattern.
3. Word Break (LeetCode 139)
   • Hint: 1D DP array. Inner loop scans backward looking for a valid dp[j].

9. Summary

• The Setup: 2D Matrix of size [M+1][N+1].
• String Indexing: Use charAt(i - 1) to match the 1-indexed DP table to the 0-indexed String.
• LCS Rule: Match $\rightarrow$ Diagonal + 1. Mismatch $\rightarrow$ Max of Top or Left.
• Edit Rule: Match $\rightarrow$ Diagonal + 0. Mismatch $\rightarrow$ Min(Top, Left, Diag) + 1.