Dynamic Programming on Strings

String dynamic programming questions fail during placement tests because students guess recurrence relations instead of mapping string prefixes to grid indices. You must define your DP state as the length of the prefix i from the first string and j from the second string, which forces the transition logic to emerge naturally from single-character choices.

The 2D State Grid

A string problem involving two inputs always builds a grid where row indices represent characters of the first string and column indices represent the second. For text1 = "abcde" and text2 = "ace", your table dp has dimensions 6 by 4 to account for empty prefixes at index 0.

The cell dp[i][j] never represents arbitrary substrings. It stores the optimal answer for the exact subproblems formed by taking the first i characters of string one and the first j characters of string two.

Filling Order for Subsequences

Longest common subsequence and edit distance require row-by-row or column-by-column traversal because every cell dp[i][j] depends exclusively on dp[i-1][j], dp[i][j-1], or dp[i-1][j-1]. If you try to compute cell dp[3][2] before filling row 2, your transition reads uninitialized memory or stale values.

For edit distance between word1 = "horse" and word2 = "ros", a mismatch at word1[i] and word2[j] means you take the minimum of deletion dp[i-1][j] + 1, insertion dp[i][j-1] + 1, and replacement dp[i-1][j-1] + 1. The base cases fill row 0 and column 0 with numbers 0 through 5 because transforming any string into an empty string takes deletions equal to its length.

A Worked Example

Consider finding the longest common subsequence for s1 = "ab" and s2 = "ac". The 3 by 3 table starts with zeros on row 0 and column 0.

At dp[1][1], characters s1[0] which is a and s2[0] which is a match, so you take dp[0][0] + 1 which yields 1. At dp[1][2], a does not match c, so you take the maximum of dp[0][2] which is 0 and dp[1][1] which is 1, giving 1.

Moving to row 2, s1[1] is b. At dp[2][1], b and a mismatch, taking the maximum of dp[1][1] and dp[2][0] to get 1. At dp[2][2], b and c mismatch, taking the maximum of dp[1][2] and dp[2][1] to get 1. The final answer at dp[2][2] is 1.

Palindromes and Distinct Variants

Longest palindromic subsequence reduces to longest common subsequence by taking the input string, reversing it, and running standard LCS on the pair. If your input is s = "bbbab", the reverse is r = "babbb", and their LCS yields 4 for "bbbb".

Distinct subsequences changes the transition from a minimum or maximum choice to a summation. When s[i-1] == t[j-1], dp[i][j] equals dp[i-1][j-1] + dp[i-1][j] because you can either use the current character match or skip it. When characters differ, dp[i][j] equals dp[i-1][j] since you must drop the character from the source string.

The Table Rule of Thumb

Define state indices as prefix lengths from 1 to n. Fill base cases on row 0 and column 0 before nested loops. Check adjacent cells i-1 and j-1 for your state transitions. Space optimize to one or two rows when only previous values matter.

Practice these exact grid patterns on DSA Tracker before your next technical round. Open a coding environment and write out the dp array dimensions for edit distance by hand right now.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Binary search trees on Wikipedia.