Back to Technology

Sequence DP: Edit Distance, Common Substring & Supersequence

September 9, 2026 Wasil Zafar 22 min read

LCS is the gateway problem of two-string DP. This lesson covers the rest of the family it unlocks: Longest Common Substring, real Edit Distance, Damerau-Levenshtein, Shortest Common Supersequence, and Longest Palindromic Subsequence.

Table of Contents

  1. Introduction & Motivation
  2. Prerequisites
  3. Longest Common Substring
  4. Edit Distance (Levenshtein)
  5. Damerau-Levenshtein Distance
  6. Shortest Common Supersequence
  7. Longest Palindromic Subsequence
  8. Complexity Comparison
  9. Applications & Alternatives
  10. Exercises
  11. Summary Cheat Sheet

1. Introduction & Motivation

Every problem in this lesson is a member of the same family: 2D DP over two strings/sequences, where the state is (position in string A, position in string B). You fill an $(m+1) \times (n+1)$ table, one axis per string, and each cell answers "what is the best value considering only the prefixes ending here?" The transition compares one character from each string and decides how to combine the answers to smaller prefixes.

Longest Common Subsequence (LCS) is the simplest member of this family: it only asks "how long is the longest sequence of characters that appears in both strings, in order, not necessarily contiguous?" Every variant in this lesson keeps that same two-pointer state design and only changes the question asked of each cell, or bolts a small addition onto the recurrence. Once you see the shared skeleton, the "new" algorithms stop feeling new.

Mastery target: Level A recognition, progressing toward Level B implementation. You should be able to look at a new string-alignment problem, recognize which member of this family it belongs to, and derive its recurrence from the LCS skeleton instead of memorizing five unrelated algorithms.

2. Prerequisites

This lesson assumes you have already worked through Part 15: Core DP Patterns – Longest Common Subsequence. That lesson builds the LCS state design and 2D table-filling technique from scratch, with a full three-language implementation. It is not repeated here — every section below either extends that recurrence directly or reuses its table. If the phrase "$dp[i][j]$ = LCS length of $text1[0..i-1]$ and $text2[0..j-1]$" is unfamiliar, read that section first.

Note that a different page in this series, dsa-interview-pattern-recognition.html, has a section titled "2D DP: Edit Distance" — but its code sample is actually LCS again, not real Edit Distance. Section 4 of this lesson implements the genuine Levenshtein recurrence, which is a different problem with a different recurrence and a different answer on the same inputs.

3. Longest Common Substring

LCS allows gaps: any subsequence that preserves relative order counts, so "abcde" and "ace" share the subsequence "ace" even though the letters are scattered through the first string. A substring is a much stricter ask — the matched characters must be contiguous in both strings, with no gaps allowed.

Core insight: Because the match must be contiguous, redefine the state as dp[i][j] = length of the common substring ending exactly at s1[i-1] and s2[j-1]. The moment characters mismatch, the run breaks — so dp[i][j] resets to 0 instead of falling back to max(dp[i-1][j], dp[i][j-1]) the way LCS does. Since the best substring can end anywhere in the table, not necessarily at the last characters of both strings, you must track the running maximum (and where it occurred) separately as you fill the table. 
def longest_common_substring(s1, s2):
    """
    Longest Common Substring (contiguous) -- distinct from LCS.
    dp[i][j] = length of the common substring ending at s1[i-1], s2[j-1].
    Time: O(m*n), Space: O(m*n)
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    best_length = 0
    best_end_in_s1 = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > best_length:
                    best_length = dp[i][j]
                    best_end_in_s1 = i
            else:
                dp[i][j] = 0  # contiguity breaks: reset, do not carry forward

    return s1[best_end_in_s1 - best_length:best_end_in_s1]

s1, s2 = "abab", "baba"
substring = longest_common_substring(s1, s2)
print(f"Longest common substring: '{substring}' (length {len(substring)})")  # 'aba' (length 3)

// Longest Common Substring (contiguous) -- distinct from LCS.
// Time: O(m*n), Space: O(m*n)
#include <iostream>
#include <string>
#include <vector>

std::string longestCommonSubstring(const std::string& s1, const std::string& s2) {
    int m = s1.size(), n = s2.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    int bestLength = 0, bestEndInS1 = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if (dp[i][j] > bestLength) {
                    bestLength = dp[i][j];
                    bestEndInS1 = i;
                }
            } else {
                dp[i][j] = 0; // contiguity breaks
            }
        }
    }
    return s1.substr(bestEndInS1 - bestLength, bestLength);
}

int main() {
    std::string s1 = "abab", s2 = "baba";
    std::string substring = longestCommonSubstring(s1, s2);
    std::cout << "Longest common substring: '" << substring
              << "' (length " << substring.size() << ")\n"; // 'aba' (length 3)
}

// Longest Common Substring (contiguous) -- distinct from LCS.
// Time: O(m*n), Space: O(m*n)
public class LongestCommonSubstring {
    static String longestCommonSubstring(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        int bestLength = 0, bestEndInS1 = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if (dp[i][j] > bestLength) {
                        bestLength = dp[i][j];
                        bestEndInS1 = i;
                    }
                } else {
                    dp[i][j] = 0; // contiguity breaks
                }
            }
        }
        return s1.substring(bestEndInS1 - bestLength, bestEndInS1);
    }

    public static void main(String[] args) {
        String s1 = "abab", s2 = "baba";
        String substring = longestCommonSubstring(s1, s2);
        System.out.println("Longest common substring: '" + substring
            + "' (length " + substring.length() + ")"); // 'aba' (length 3)
    }
}
Hand Trace

Trace on "abab" vs "baba"

Build the 5×5 table (rows = s1 = "abab", columns = s2 = "baba"). Row/column 0 are all zero.

∅baba
∅00000
a00101
b01020
a00203
b01030

The maximum value 3 first appears at dp[3][4] (row for s1[0..2]="aba", column for s2[0..3]="baba" ending in "a"), giving substring "aba". It appears again at dp[4][3]=3, corresponding to substring "bab" — both are valid length-3 answers. Notice the bottom-right corner dp[4][4] is 0: if you had only read off the final cell, as LCS does, you would have missed the answer entirely. That is exactly why the running maximum must be tracked separately from the table itself.

4. Edit Distance (Levenshtein Distance)

Edit Distance asks a different question again: not "how much do two strings share," but "how many single-character operations does it take to transform one string into the other?" The three allowed operations are insertion, deletion, and replacement (substitution), each costing one edit.

Core insight: Define dp[i][j] = minimum operations to convert s1[0..i) into s2[0..j). Base cases dp[i][0] = i and dp[0][j] = j represent deleting everything or inserting everything from scratch. If the current characters match, that character costs nothing and the answer is whatever it cost to convert the shorter prefixes: dp[i][j] = dp[i-1][j-1]. On a mismatch, one edit is spent, and you take the cheapest of the three neighboring cells — delete from s1 (dp[i-1][j]), insert into s1 (dp[i][j-1]), or replace (dp[i-1][j-1]): $$dp[i][j] = 1 + \min\big(dp[i-1][j],\, dp[i][j-1],\, dp[i-1][j-1]\big)$$

This is genuinely different code from LCS — the mismatch branch adds 1 and looks at three neighbors including the diagonal, where LCS's mismatch branch adds nothing and looks at only two neighbors (never the diagonal). Confusing the two recurrences is precisely the mistake in the site's mislabeled "2D DP: Edit Distance" section; the implementation below is the real one.

def edit_distance(s1, s2):
    """
    Levenshtein distance: minimum insert/delete/replace operations
    to convert s1 into s2. dp[i][j] = edit distance of s1[0:i], s2[0:j].
    Time: O(m*n), Space: O(m*n)
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i  # delete all i characters of s1
    for j in range(n + 1):
        dp[0][j] = j  # insert all j characters of s2

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # characters match, no cost
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # delete from s1
                    dp[i][j-1],    # insert into s1
                    dp[i-1][j-1],  # replace
                )
    return dp[m][n]

print(edit_distance("horse", "ros"))  # 3

// Levenshtein distance: real Edit Distance, not LCS.
// Time: O(m*n), Space: O(m*n)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int editDistance(const std::string& s1, const std::string& s2) {
    int m = s1.size(), n = s2.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + std::min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
            }
        }
    }
    return dp[m][n];
}

int main() {
    std::cout << editDistance("horse", "ros") << '\n'; // 3
}

// Levenshtein distance: real Edit Distance, not LCS.
// Time: O(m*n), Space: O(m*n)
public class EditDistance {
    static int editDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(editDistance("horse", "ros")); // 3
    }
}

Trace "horse" → "ros": replace 'h' with 'r' ("rorse"), delete 'r' ("rose"), delete 'e' ("ros") — three operations, matching dp[5][3] = 3.

5. Damerau-Levenshtein Distance

Real-world typos are often two adjacent characters swapped ("hte" for "the"). Under plain Edit Distance that swap costs two operations (two replacements, or a delete plus an insert). Damerau-Levenshtein adds exactly one new operation: swapping two adjacent characters counts as a single edit, not two.

The one addition: after computing the usual match/insert/delete/replace value for dp[i][j], check whether the last two characters of each prefix are a swapped pair — s1[i-1] == s2[j-2] and s1[i-2] == s2[j-1]. If so, the table already knows the cost of fixing everything before that pair at dp[i-2][j-2], so the transposition lets you skip both mismatched characters for the price of one edit: $$dp[i][j] = \min\big(dp[i][j],\, dp[i-2][j-2] + 1\big)$$ This table-based extension is what most tutorials teach under the name Damerau-Levenshtein; it is restricted to transposing adjacent, not-yet-edited characters (formally the "Optimal String Alignment" distance), which is sufficient for the vast majority of typo-correction use cases. 
def damerau_levenshtein(s1, s2):
    """
    Edit Distance plus adjacent-transposition as a single operation.
    Extends edit_distance() with one extra case.
    Time: O(m*n), Space: O(m*n)
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

            # 4th case: adjacent transposition counts as a single edit
            if (i > 1 and j > 1
                    and s1[i-1] == s2[j-2]
                    and s1[i-2] == s2[j-1]):
                dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1)

    return dp[m][n]

print(damerau_levenshtein("CA", "AC"))       # 1 (one adjacent swap)
print(damerau_levenshtein("horse", "ros"))   # 3 (no transposition helps here)

// Edit Distance plus adjacent-transposition as a single operation.
// Time: O(m*n), Space: O(m*n)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int damerauLevenshtein(const std::string& s1, const std::string& s2) {
    int m = s1.size(), n = s2.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + std::min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
            }
            // 4th case: adjacent transposition counts as a single edit
            if (i > 1 && j > 1 && s1[i-1] == s2[j-2] && s1[i-2] == s2[j-1]) {
                dp[i][j] = std::min(dp[i][j], dp[i-2][j-2] + 1);
            }
        }
    }
    return dp[m][n];
}

int main() {
    std::cout << damerauLevenshtein("CA", "AC") << '\n';     // 1
    std::cout << damerauLevenshtein("horse", "ros") << '\n';  // 3
}

// Edit Distance plus adjacent-transposition as a single operation.
// Time: O(m*n), Space: O(m*n)
public class DamerauLevenshtein {
    static int damerauLevenshtein(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
                }
                // 4th case: adjacent transposition counts as a single edit
                if (i > 1 && j > 1 && s1.charAt(i-1) == s2.charAt(j-2) && s1.charAt(i-2) == s2.charAt(j-1)) {
                    dp[i][j] = Math.min(dp[i][j], dp[i-2][j-2] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(damerauLevenshtein("CA", "AC"));      // 1
        System.out.println(damerauLevenshtein("horse", "ros"));  // 3
    }
}

Trace "CA" → "AC": plain Edit Distance needs 2 (replace both characters). With the transposition case, dp[2][2] checks s1[1]='A' == s2[0]='A' and s1[0]='C' == s2[1]='C' — both hold, so dp[2][2] = min(2, dp[0][0] + 1) = 1: a single adjacent swap.

6. Shortest Common Supersequence

The Shortest Common Supersequence (SCS) is the shortest string that contains both s1 and s2 as subsequences (not substrings — order matters, gaps are fine).

Core insight: $$\text{len(SCS)} = \text{len}(s1) + \text{len}(s2) - \text{LCS}(s1, s2)$$ Every character of both strings must appear in the supersequence, but characters shared by the LCS only need to appear once instead of once per string — they can be reused to satisfy both subsequence requirements simultaneously. Every non-shared character still costs one slot. The LCS length itself is computed exactly as in Part 15; it is not re-derived here.

The length formula only answers "how long," not "what string." To actually reconstruct the supersequence, walk the same LCS dp table backward from (m, n): whenever the characters match, they are shared — emit the character once and step both pointers diagonally. Otherwise, step toward whichever neighbor holds the table's current value (the side that was not discounted by the match), emitting that side's character, since that character is not part of the shared LCS and must be preserved. Once one pointer reaches 0, drain the remaining characters from the other string as-is.

def shortest_common_supersequence(s1, s2):
    """
    Builds the LCS table (see Part 15's LCS lesson), then walks it
    backward to merge s1 and s2 into their shortest supersequence.
    len(SCS) = len(s1) + len(s2) - LCS(s1, s2).
    Time: O(m*n), Space: O(m*n)
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    merged = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            merged.append(s1[i-1])   # shared character: emit once
            i -= 1
            j -= 1
        elif dp[i-1][j] >= dp[i][j-1]:
            merged.append(s1[i-1])   # s1's character is not shared, keep it
            i -= 1
        else:
            merged.append(s2[j-1])   # s2's character is not shared, keep it
            j -= 1
    while i > 0:
        merged.append(s1[i-1])
        i -= 1
    while j > 0:
        merged.append(s2[j-1])
        j -= 1

    merged.reverse()
    return "".join(merged)

result = shortest_common_supersequence("abac", "cab")
print(result, len(result))  # cabac 5

// Builds the LCS table, then walks it backward to reconstruct
// the shortest common supersequence.
// Time: O(m*n), Space: O(m*n)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::string shortestCommonSupersequence(const std::string& s1, const std::string& s2) {
    int m = s1.size(), n = s2.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
        }
    }

    std::string merged;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (s1[i-1] == s2[j-1]) {
            merged += s1[i-1];
            i--; j--;
        } else if (dp[i-1][j] >= dp[i][j-1]) {
            merged += s1[i-1];
            i--;
        } else {
            merged += s2[j-1];
            j--;
        }
    }
    while (i > 0) { merged += s1[i-1]; i--; }
    while (j > 0) { merged += s2[j-1]; j--; }

    std::reverse(merged.begin(), merged.end());
    return merged;
}

int main() {
    std::string result = shortestCommonSupersequence("abac", "cab");
    std::cout << result << " " << result.size() << '\n'; // cabac 5
}

// Builds the LCS table, then walks it backward to reconstruct
// the shortest common supersequence.
// Time: O(m*n), Space: O(m*n)
public class ShortestCommonSupersequence {
    static String shortestCommonSupersequence(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }

        StringBuilder merged = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                merged.append(s1.charAt(i-1));
                i--; j--;
            } else if (dp[i-1][j] >= dp[i][j-1]) {
                merged.append(s1.charAt(i-1));
                i--;
            } else {
                merged.append(s2.charAt(j-1));
                j--;
            }
        }
        while (i > 0) { merged.append(s1.charAt(i-1)); i--; }
        while (j > 0) { merged.append(s2.charAt(j-1)); j--; }

        return merged.reverse().toString();
    }

    public static void main(String[] args) {
        String result = shortestCommonSupersequence("abac", "cab");
        System.out.println(result + " " + result.length()); // cabac 5
    }
}

Trace "abac" and "cab": LCS length is 2 (e.g. "ab"), so the formula predicts $4 + 3 - 2 = 5$. Walking the table backward from (4,3) produces "cabac" — length 5, and it does contain both "abac" and "cab" as subsequences (positions 1,2,3,4 spell "abac"; positions 0,1,2 spell "cab").

7. Longest Palindromic Subsequence

The Longest Palindromic Subsequence (LPS) of a string s is the longest subsequence of s that reads the same forwards and backwards.

Core insight: $$\text{LPS}(s) = \text{LCS}(s, \text{reverse}(s))$$ A subsequence common to s read forward and s read backward must, by definition, read identically in both directions — and a string that reads the same forward and backward is exactly a palindrome. So instead of inventing a new recurrence, run the LCS table-filling technique on s against its own reverse, and the resulting length is the longest palindromic subsequence length.

Each implementation below is self-contained: it builds its own reverse of s and fills the same LCS-shaped table inline, rather than calling a separate LCS function.

def longest_palindromic_subsequence(s):
    """
    LPS(s) = LCS(s, reverse(s)). A subsequence common to s (read
    forward) and s (read backward) must read the same both ways --
    i.e. it is a palindrome -- so the LCS table built on s and its
    reverse directly gives the longest palindromic subsequence length.
    Time: O(n^2), Space: O(n^2)
    """
    t = s[::-1]
    n = len(s)
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[n][n]

print(longest_palindromic_subsequence("bbbab"))  # 4 ("bbbb")

// LPS(s) = LCS(s, reverse(s)), computed inline (self-contained).
// Time: O(n^2), Space: O(n^2)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int longestPalindromicSubsequence(const std::string& s) {
    std::string t(s.rbegin(), s.rend());
    int n = s.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[n][n];
}

int main() {
    std::cout << longestPalindromicSubsequence("bbbab") << '\n'; // 4
}

// LPS(s) = LCS(s, reverse(s)), computed inline (self-contained).
// Time: O(n^2), Space: O(n^2)
public class LongestPalindromicSubsequence {
    static int longestPalindromicSubsequence(String s) {
        String t = new StringBuilder(s).reverse().toString();
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i-1) == t.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[n][n];
    }

    public static void main(String[] args) {
        System.out.println(longestPalindromicSubsequence("bbbab")); // 4
    }
}

8. Complexity Comparison Table

TechniqueState DefinitionRecurrence (brief)TimeSpace
Longest Common Substringdp[i][j] = length of common substring ending at s1[i-1], s2[j-1]match: dp[i-1][j-1]+1; else 0 (track max separately)$O(mn)$$O(mn)$
Edit Distancedp[i][j] = min ops to turn s1[0..i) into s2[0..j)match: dp[i-1][j-1]; else 1+min(del, ins, replace)$O(mn)$$O(mn)$
Damerau-Levenshteinsame as Edit Distanceas above, plus dp[i-2][j-2]+1 when adjacent chars are swapped$O(mn)$$O(mn)$
Shortest Common Supersequencereuses LCS's dp[i][j]; string reconstructed by backward walklength = len(s1)+len(s2)-LCS(s1,s2); walk emits non-shared chars from whichever side matches the current cell$O(mn)$$O(mn)$
Longest Palindromic Subsequencedp[i][j] = LCS length of s[0..i) and reverse(s)[0..j)match: dp[i-1][j-1]+1; else max(dp[i-1][j], dp[i][j-1])$O(n^2)$$O(n^2)$

9. Applications & Alternatives

Where this family shows up

Real systems built on these recurrences

  • Spell-checkers and autocorrect: Edit Distance and Damerau-Levenshtein rank candidate corrections by how many typo-style operations separate them from the typed word.
  • DNA sequence alignment: bioinformatics tools use Edit-Distance-style scoring (often with custom gap and mismatch penalties) to align genetic sequences, and Longest Common Substring to find shared genetic motifs.
  • Diff tools: line-based and character-based diff utilities are built on LCS and Edit-Distance-style alignment to find the minimal set of insertions/deletions between two file versions.
  • Autocomplete and fuzzy search: ranking suggestions by bounded Edit Distance lets a search box tolerate small typos while still matching the intended term.

Alternatives exist when the exact DP tables above are too slow for very long strings: bounded Edit Distance search (only compute cells within a diagonal band) trades generality for speed when you only care whether the distance is below a small threshold, and suffix automata or suffix arrays can find Longest Common Substrings in $O(m+n)$ instead of $O(mn)$ when the inputs are large. Choose the exact DP when strings are short or the exact edit script is needed; choose the specialized structure when only a yes/no or a length answer is required at scale.

10. Exercises

Easy

  1. Find the Longest Common Substring of "programming" and "gaming", and state its length.

Medium

  1. Compute the Edit Distance between "sunday" and "saturday" under custom operation costs: replace costs 2, insert and delete each cost 1. (Hint: the recurrence's mismatch branch becomes min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+2).)

Hard

  1. Extend the standard Edit Distance implementation to reconstruct the actual sequence of operations (not just the count) by walking the completed dp table backward from (m, n): at each cell, check which of match, replace, delete, or insert produced the stored value, emit that operation, and step to the corresponding neighbor.
Mastery challenge: A search-autocomplete service must suggest corrections for a mistyped query against a dictionary of a million words. Decide which member of this family (or which alternative from Section 9) fits the latency budget, justify the choice with the complexity table above, and explain what changes if the dictionary is static versus updated in real time.

Review rhythm: tomorrow, re-derive all five recurrences from the shared LCS skeleton without looking them up; next week, implement Edit Distance and its operation-reconstruction variant from memory; several weeks later, recognize which member of this family a new interview problem belongs to before writing any code.

11. Summary Cheat Sheet

  • All five techniques share the LCS state design: a 2D table indexed by (position in string A, position in string B).
  • Longest Common Substring resets to 0 on mismatch (contiguity) and needs a separately tracked running maximum.
  • Edit Distance's mismatch branch costs 1 and checks all three neighbors, including the diagonal — unlike LCS.
  • Damerau-Levenshtein adds one extra case to Edit Distance: an adjacent-transposition check against dp[i-2][j-2].
  • Shortest Common Supersequence length is len(s1) + len(s2) - LCS(s1, s2); the string itself requires backtracking through the LCS table.
  • Longest Palindromic Subsequence is just LCS of a string against its own reverse.
  • All five run in $O(mn)$ time and space (or $O(n^2)$ for the single-string LPS case).

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Browse the complete curriculum and practical project sequence.

Open the DSA Hub
Part 15: Core DP Patterns

Build the LCS state design and 2D table-filling technique this lesson extends, alongside 0/1 Knapsack and Coin Change.

Read the Core DP Patterns Guide
The LIS Family

Apply the same DP-family thinking to Longest Increasing Subsequence and its variants.

Read the LIS Family Guide