String Dynamic Programming

String dynamic programming solves problems whose best answer depends on prefixes of one or more strings. Instead of exploring exponentially many subsequences or edit sequences, define a state for two prefix lengths and combine previously solved smaller states. Two foundational examples are the longest common subsequence (LCS) and Levenshtein edit distance. LCS asks for the longest sequence of characters appearing in both strings in order, with gaps allowed. Edit distance asks for the fewest insertions, deletions, and substitutions needed to transform one string into the other. They use similarly shaped tables but different meanings and transitions. The complete program implements both and reconstructs one LCS.

Prerequisites: Basic dynamic programming, arrays, strings, induction, maximum/minimum recurrences.

Build the idea

1. 1. Prefix lengths avoid boundary confusion

   Let n=|A| and m=|B|. Table cell (i,j) describes A[0..i-1] and B[0..j-1], so row 0 and column 0 represent empty prefixes. String characters remain 0-based even though DP prefix lengths run from 0 through n or m. This convention makes deleting the last character a transition to i-1 and matching final characters a transition to (i-1,j-1). Always define the state in words before writing a recurrence: the table shape alone does not reveal whether a cell stores a maximum length or a minimum cost.

2. 2. LCS recurrence and why it works

   Define L[i][j] as the LCS length of the two prefixes. If A[i-1]=B[j-1], an optimal common subsequence can end with that shared character; append it to an LCS of the shorter prefixes, giving L[i-1][j-1]+1. If the last characters differ, a common subsequence cannot use both as its final matched character. It must omit at least one: take max(L[i-1][j],L[i][j-1]). Both choices remain legal subsequences, so taking the better one is sufficient. If either prefix is empty, the answer is zero.

3. 3. A small LCS table

   For A=abc and B=ac, the row for the empty A prefix is [0,0,0]. After a, the row is [0,1,1]; after ab it remains [0,1,1]; after abc it becomes [0,1,2]. The answer is 2, spelling ac. This is a subsequence, not a substring: the b is skipped. For abcde and ace, matches a,c,e produce length 3 even though those characters are not adjacent in the first text. LCS is useful when relative order matters but intervening characters may be irrelevant.

4. 4. Reconstruct one optimal subsequence

   Start at (n,m). When the current last characters agree, record that character and move diagonally. Otherwise move to a neighbor with the same optimal LCS value: up if L[i-1][j]≥L[i][j-1], else left. Stop when one prefix becomes empty and reverse the recorded characters. The inequality makes tie-breaking deterministic, but does not guarantee the lexicographically smallest LCS. Every move preserves the possibility of an optimal solution, and each diagonal match contributes one character, so the reconstructed length equals L[n][m].

5. 5. Edit distance uses costs, not lengths

   Define D[i][j] as the minimum cost to transform the first i characters of A into the first j characters of B. If A is empty, insert j characters: D[0][j]=j. If B is empty, delete i characters: D[i][0]=i. For nonempty prefixes, consider deleting A's last character (D[i-1][j]+1), inserting B's last character (D[i][j-1]+1), or matching/substituting the last characters (D[i-1][j-1]+cost), where cost is 0 for equality and 1 otherwise. Take the minimum. These cases classify the final alignment action, so every optimal transformation is represented.

6. 6. Work an edit example and compare meanings

   kitten becomes sitting in three unit-cost operations: substitute k→s, substitute e→i, and append g. Its edit distance is 3. Its LCS length is 4, with ittn as one answer. Do not compute this edit distance as n+m-2*LCS: that formula is for insertion/deletion-only distance, where substitutions are unavailable or cost two. With a→b, unit-cost edit distance is 1, but LCS is empty and the insertion/deletion-only distance is 2. The chosen operation model is part of the problem statement and must determine the recurrence.

7. 7. Evaluation order and a correctness argument

   Both tables depend only on smaller prefix lengths: above, left, or diagonal. Filling rows from top to bottom and columns from left to right ensures these states already exist. Base rows anchor an induction on i+j. Assuming all shorter prefix pairs are solved, the recurrence examines every possible final choice and combines it with an optimal smaller solution. Choosing maximum for LCS or minimum for edit distance therefore gives the correct current answer. This reasoning is more reliable than copying a familiar-looking formula from a different string problem.

8. 8. Memory tradeoffs and appropriate use

   Two full tables make the implementation and reconstruction easy to inspect. If only lengths or distance are needed, keep two rows and reduce memory to O(min(n,m)), making the shorter string the column dimension. Reconstructing a sequence from rolling rows needs additional techniques such as Hirschberg’s algorithm; it does not happen automatically. Quadratic time becomes impractical for very long strings, so check the product n*m against limits. Specialized algorithms or banded DP may help under extra assumptions, but changing the recurrence without those assumptions can silently change the answer.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a,b;
    getline(cin,a);
    getline(cin,b);
    int n=(int)a.size(),m=(int)b.size();
    vector<vector<int>>lcs(n+1,vector<int>(m+1));
    vector<vector<int>>edit(n+1,vector<int>(m+1));
    // Empty-prefix edit costs are insertions or deletions, not zero.
    for(int i=0;i<=n;i++){
        edit[i][0]=i;
    }
    for(int j=0;j<=m;j++){
        edit[0][j]=j;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i-1]==b[j-1]){
                lcs[i][j]=lcs[i-1][j-1]+1;
            }
            else{
                lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);
            }
            int cost=(a[i-1]==b[j-1]?0:1);
            // Deletion, insertion, and substitution/match form the three cases.
            edit[i][j]=min({edit[i-1][j]+1,edit[i][j-1]+1,edit[i-1][j-1]+cost});
        }
    }
    string answer;
    int i=n,j=m;
    while(i>0&&j>0){
        if(a[i-1]==b[j-1]){
            answer.push_back(a[i-1]);
            i--;
            j--;
        }
        else if(lcs[i-1][j]>=lcs[i][j-1]){
            i--; // Deterministic, not lexicographic.
        }
        else{
            j--;
        }
    }
    reverse(answer.begin(),answer.end()); // Backtracking found characters right-to-left.
    cout<<lcs[n][m]<<'\n'<<answer<<'\n'<<edit[n][m]<<'\n';
}

Complexity analysis

Both table constructions together take O(nm) time. Full storage is O(nm), and LCS reconstruction takes O(n+m) time with O(min(n,m)) output space. Length-only LCS or edit distance can use O(min(n,m)) rolling-row space, but that optimization is not used in this reconstruction program.

Example input and output

Two complete text lines A and B, either possibly empty and with spaces preserved. Lengths satisfy 0≤n,m≤2000. Output LCS length on line 1, one reconstructed LCS on line 2 (blank when empty), and unit-cost insertion/deletion/substitution edit distance on line 3. Characters are compared as bytes; substitutions cost 1.

Input

kitten
sitting

Output

4
ittn
3

ittn occurs in order in both strings, and no common subsequence has length 5. Transform kitten to sitting using two substitutions and one insertion, for total edit cost 3.

Practical applications

Diff and sequence comparison; approximate matching; minimal edit scripts after backtracking; subsequence alignment; related DP for longest palindromic subsequences, wildcard matching, and weighted alignment, each with its own state definition.

Check your understanding

For unit-cost substitutions, is edit distance always n+m−2*LCS?

Put it into practice

Reconstruct and print one optimal edit script, including substitutions, insertions, and deletions.