SyntaxPilot
Courses/DSA and Coding Problems/Lesson 67
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 67 of 90

Longest common subsequence

queued

These are the notes for DSA episode 67. You typed out Mum's chai recipe for the family group, and she sent it back edited: ginger gone, cardamom added, milk and sugar swapped. Which steps did she keep, in the same order? That's the longest common subsequence (LCS), and it's exactly what git diff computes between two versions of a file. We write the obvious recursion (Time Limit Exceeded on two 30-letter strings), see why it repeats itself, build the table dp[i][j] (match → diagonal + 1, otherwise max of up and left), walk it back to print the subsequence and a real line-by-line diff, and shrink it to two rows. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).

The problem, in real life

The edited recipe In code
Your version: 6 steps string / array a
Mum's version: 6 steps string / array b
One step (one line) one character a[i] (or one line a[i])
Steps kept, same order, gaps allowed a common subsequence
The most steps kept the longest common subsequence
Steps not kept deleted (-) or added (+) lines: a diff

Every word, from zero

  • Subsequence: what's left after deleting any letters from a string, keeping the order. "ace" is a subsequence of "abcde".
  • Substring: one unbroken piece of a string. "bcd" is a substring of "abcde"; "ace" is not.
  • Common subsequence: a string that is a subsequence of both strings.
  • LCS: the longest common subsequence (or its length).
  • Prefix: the first i letters of a string. The empty prefix has i = 0.
  • State: the few numbers that fully describe a sub-problem; here (i, j): the first i letters of a and the first j letters of b.
  • Recurrence: the rule that builds a state's answer from smaller states.
  • Memoization (top-down): the recursion plus a notebook of answers already computed.
  • Tabulation (bottom-up): filling a table from the smallest sub-problems up.
  • Walk back (reconstruction): following the table from the answer cell back to the start to recover the choices.
  • Diff: the list of lines kept, deleted and added between two versions of a text.
  • Rolling array: keeping only the row(s) the next row needs.

Problem statement

Given two strings a and b, return the length of their longest common subsequence. If there is none, return 0. (LeetCode 1143.)

a b Answer
"abcde" "ace" 3 (ace)
"AGGTAB" "GXTXAYB" 4 (GTAB)
"abc" "abc" 3 (identical)
"abc" "def" 0 (nothing in common)
"" "abc" 0 (empty string)

Typical constraints: 1 ≤ a.length, b.length ≤ 1000, lowercase English letters.

Obvious correct idea: look at the last letters

Let go(i, j) be the LCS of the first i letters of a and the first j letters of b.

  • If either is empty (i == 0 or j == 0): 0.
  • If the last letters match (a[i-1] == b[j-1]): keep that letter, 1 + go(i - 1, j - 1).
  • Otherwise one of the two last letters is unused: max(go(i - 1, j), go(i, j - 1)).
import java.util.*;

public class Main {
    static int lcs(String a, String b) {
        return go(a, b, a.length(), b.length());
    }
    static int go(String a, String b, int i, int j) {
        if (i == 0 || j == 0) return 0;
        if (a.charAt(i - 1) == b.charAt(j - 1)) return 1 + go(a, b, i - 1, j - 1);
        return Math.max(go(a, b, i - 1, j), go(a, b, i, j - 1));
    }
    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace"));
        System.out.println(lcs("AGGTAB", "GXTXAYB"));
        System.out.println(lcs("abc", "abc"));
        System.out.println(lcs("abc", "def"));
        System.out.println(lcs("", "abc"));
    }
}
3
4
3
0
0

All correct. Now two strings of 30 letters each:

import java.util.*;

public class Main {
    static int lcs(String a, String b) {
        return go(a, b, a.length(), b.length());
    }
    static int go(String a, String b, int i, int j) {
        if (i == 0 || j == 0) return 0;
        if (a.charAt(i - 1) == b.charAt(j - 1)) return 1 + go(a, b, i - 1, j - 1);
        return Math.max(go(a, b, i - 1, j), go(a, b, i, j - 1));
    }
    public static void main(String[] args) {
        StringBuilder x = new StringBuilder(), y = new StringBuilder();
        for (int i = 0; i < 30; i++) {
            x.append((char) ('a' + i * 7 % 26));
            y.append((char) ('a' + i * 11 % 26));
        }
        long t0 = System.nanoTime();
        int best = lcs(x.toString(), y.toString());
        long ms0 = (System.nanoTime() - t0) / 1000000;
        System.out.println("30 letters: " + best + ", " + ms0 + " ms");
    }
}
Time Limit Exceeded (no output after 25 seconds)

Why is it slow?

Every mismatch makes two calls, so the work can grow like 2^(n + m). But a call depends only on (i, j), and different paths land on the same pair: dropping a letter from a then from b, or from b then from a, both reach (i - 1, j - 1). There are only (n + 1) × (m + 1) different pairs: 31 × 31 = 961 for 30 letters. The recursion solves the same few hundred questions billions of times, exactly like Fibonacci (episode 62) and the knapsack (episode 65).

The key insight: the DP table

  1. State: dp[i][j] = LCS length of a's first i letters and b's first j letters.
  2. Match (a[i-1] == b[j-1]): dp[i][j] = dp[i-1][j-1] + 1 (the diagonal plus one).
  3. No match: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (the bigger of up and left).
  4. Base: row 0 and column 0 are all 0 (an empty prefix has nothing in common).
  5. Answer: dp[n][m], the bottom-right cell.

By hand: a = "ace", b = "abcde"

'' a b c d e
'' 0 0 0 0 0 0
a 0 1 1 1 1 1
c 0 1 1 2 2 2
e 0 1 1 2 2 3

The bold cells are the matches (diagonal + 1). Every other cell copies the bigger of up and left. The answer is the corner, 3, and walking back along the diagonal jumps spells a, c, e.

Solution in Java: the table

import java.util.*;

public class Main {
    static int lcs(String a, String b) {
        int n = a.length(), m = b.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.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][m];
    }
    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace"));
        System.out.println(lcs("AGGTAB", "GXTXAYB"));
        System.out.println(lcs("abc", "abc"));
        System.out.println(lcs("abc", "def"));
        System.out.println(lcs("", "abc"));
    }
}
3
4
3
0
0

The same table on the 30 letters that timed out, and on two 3,000-letter strings (9 million cells):

import java.util.*;

public class Main {
    static int lcs(String a, String b) {
        int n = a.length(), m = b.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.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][m];
    }
    public static void main(String[] args) {
        StringBuilder x = new StringBuilder(), y = new StringBuilder();
        for (int i = 0; i < 30; i++) {
            x.append((char) ('a' + i * 7 % 26));
            y.append((char) ('a' + i * 11 % 26));
        }
        long t0 = System.nanoTime();
        int best = lcs(x.toString(), y.toString());
        long ms0 = (System.nanoTime() - t0) / 1000000;
        System.out.println("30 letters: " + best + ", " + ms0 + " ms");
        StringBuilder p = new StringBuilder(), q = new StringBuilder();
        for (int i = 0; i < 3000; i++) {
            p.append((char) ('a' + i * 7 % 26));
            q.append((char) ('a' + i * 11 % 26));
        }
        long t1 = System.nanoTime();
        int b2 = lcs(p.toString(), q.toString());
        long ms1 = (System.nanoTime() - t1) / 1000000;
        System.out.println("3000 letters: " + b2 + ", " + ms1 + " ms");
    }
}
30 letters: 12, 0 ms
3000 letters: 1154, 73 ms

Top-down: the recursion plus a notebook

import java.util.*;

public class Main {
    static int[][] memo;
    static int lcs(String a, String b) {
        memo = new int[a.length() + 1][b.length() + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        return go(a, b, a.length(), b.length());
    }
    static int go(String a, String b, int i, int j) {
        if (i == 0 || j == 0) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        if (a.charAt(i - 1) == b.charAt(j - 1)) return memo[i][j] = 1 + go(a, b, i - 1, j - 1);
        return memo[i][j] = Math.max(go(a, b, i - 1, j), go(a, b, i, j - 1));
    }
    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace"));
        System.out.println(lcs("AGGTAB", "GXTXAYB"));
        StringBuilder x = new StringBuilder(), y = new StringBuilder();
        for (int i = 0; i < 30; i++) {
            x.append((char) ('a' + i * 7 % 26));
            y.append((char) ('a' + i * 11 % 26));
        }
        long t0 = System.nanoTime();
        int best = lcs(x.toString(), y.toString());
        long ms0 = (System.nanoTime() - t0) / 1000000;
        System.out.println("30 letters: " + best + ", " + ms0 + " ms");
    }
}
3
4
30 letters: 12, 0 ms

Same answers, each (i, j) solved once. For very long strings the recursion gets about n + m deep, so the bottom-up table is the safer choice in Java (no StackOverflowError).

Which letters? Walk the table back

Start at (n, m). If the letters match, that letter is in the answer: note it, go diagonally. Otherwise step to the bigger of up and left (that's where the value came from). The letters come out backwards, so reverse at the end.

import java.util.*;

public class Main {
    static String lcsString(String a, String b) {
        int n = a.length(), m = b.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1) ? dp[i - 1][j - 1] + 1
                         : Math.max(dp[i - 1][j], dp[i][j - 1]);
        StringBuilder sb = new StringBuilder();
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                sb.append(a.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
            else j--;
        }
        return sb.reverse().toString();
    }
    public static void main(String[] args) {
        System.out.println(lcsString("abcde", "ace"));
        System.out.println(lcsString("AGGTAB", "GXTXAYB"));
        System.out.println(lcsString("ABCBDAB", "BDCABA"));
    }
}
ace
GTAB
BCBA

When up and left are equal there are several LCSs of the same length (ABCBDAB / BDCABA also has BDAB); any one of them is correct.

You just invented diff

Use whole lines instead of letters (compare with equals). Walking back: a match is a kept line, stepping left is a line added in the new version (+), stepping up is a line deleted from the old one (-).

import java.util.*;

public class Main {
    static void diff(String[] a, String[] b) {
        int n = a.length, m = b.length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] = a[i - 1].equals(b[j - 1]) ? dp[i - 1][j - 1] + 1
                         : Math.max(dp[i - 1][j], dp[i][j - 1]);
        List<String> out = new ArrayList<>();
        int i = n, j = m;
        while (i > 0 || j > 0) {
            if (i > 0 && j > 0 && a[i - 1].equals(b[j - 1])) {
                out.add("  " + a[i - 1]);
                i--;
                j--;
            } else if (j > 0 && (i == 0 || dp[i][j - 1] >= dp[i - 1][j])) {
                out.add("+ " + b[--j]);
            } else {
                out.add("- " + a[--i]);
            }
        }
        Collections.reverse(out);
        for (String s : out) System.out.println(s);
    }
    public static void main(String[] args) {
        String[] mine = {"boil water", "add ginger", "add tea leaves",
                         "add sugar", "add milk", "strain"};
        String[] mum = {"boil water", "add tea leaves", "add milk",
                        "add sugar", "add cardamom", "strain"};
        diff(mine, mum);
    }
}
  boil water
- add ginger
  add tea leaves
- add sugar
  add milk
+ add sugar
+ add cardamom
  strain

Four steps kept (boil water, tea leaves, milk, strain): the LCS. Keeping "add milk" or "add sugar" is a tie (both give 4); this walk back keeps milk, so sugar shows as deleted and then added again. Real diff tools (git diff, diff -u) are built on the same idea, with faster algorithms for huge files.

Two rows instead of a table

A cell only reads up, left and the up-left diagonal, all in the current row or the row above. So keep two rows, prev and cur, and swap them after every letter of a. (You lose the walk back: for the letters or a diff, keep the full table.)

import java.util.*;

public class Main {
    static int lcs(String a, String b) {
        int m = b.length();
        int[] prev = new int[m + 1], cur = new int[m + 1];
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= m; j++)
                cur[j] = a.charAt(i - 1) == b.charAt(j - 1) ? prev[j - 1] + 1
                       : Math.max(prev[j], cur[j - 1]);
            int[] t = prev;
            prev = cur;
            cur = t;
        }
        return prev[m];
    }
    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace"));
        System.out.println(lcs("AGGTAB", "GXTXAYB"));
        System.out.println(lcs("abc", "abc"));
        System.out.println(lcs("abc", "def"));
        System.out.println(lcs("", "abc"));
        StringBuilder u = new StringBuilder(), v = new StringBuilder();
        for (int i = 0; i < 10000; i++) {
            u.append((char) ('a' + i * 7 % 26));
            v.append((char) ('a' + i * 11 % 26));
        }
        long t2 = System.nanoTime();
        int b3 = lcs(u.toString(), v.toString());
        long ms2 = (System.nanoTime() - t2) / 1000000;
        System.out.println("10000 letters: " + b3 + ", " + ms2 + " ms");
    }
}
3
4
3
0
0
10000 letters: 3846, 278 ms

A full 10,000 × 10,000 table of ints would need about 400 MB; two rows need about 80 KB.

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

// Longest common subsequence: two rows, prev and cur.
int lcs(const string& a, const string& b) {
    int m = b.size();
    vector<int> prev(m + 1, 0), cur(m + 1, 0);
    for (size_t i = 1; i <= a.size(); i++) {
        for (int j = 1; j <= m; j++)
            cur[j] = a[i - 1] == b[j - 1] ? prev[j - 1] + 1 : max(prev[j], cur[j - 1]);
        swap(prev, cur);
    }
    return prev[m];
}

// The full table, walked back to print the subsequence itself.
string lcsString(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
    string s;
    for (int i = n, j = m; i > 0 && j > 0;) {
        if (a[i - 1] == b[j - 1]) { s += a[i - 1]; i--; j--; }
        else if (dp[i - 1][j] >= dp[i][j - 1]) i--;
        else j--;
    }
    reverse(s.begin(), s.end());
    return s;
}

int main() {
    cout << lcs("abcde", "ace") << "\n";
    cout << lcs("AGGTAB", "GXTXAYB") << "\n";
    cout << lcs("abc", "abc") << "\n";
    cout << lcs("abc", "def") << "\n";
    cout << lcs("", "abc") << "\n";
    cout << lcsString("ABCBDAB", "BDCABA") << "\n";
    string u, v;
    for (int i = 0; i < 10000; i++) { u += char('a' + i * 7 % 26); v += char('a' + i * 11 % 26); }
    cout << lcs(u, v) << "\n";
}
3
4
3
0
0
BCBA
3846

The same solution in Python

# Longest common subsequence: two rows, prev and cur.
def lcs(a, b):
    m = len(b)
    prev = [0] * (m + 1)
    for ch in a:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            cur[j] = prev[j - 1] + 1 if ch == b[j - 1] else max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

# The full table, walked back to print the subsequence itself.
def lcs_string(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            dp[i][j] = dp[i - 1][j - 1] + 1 if a[i - 1] == b[j - 1] else max(dp[i - 1][j], dp[i][j - 1])
    out, i, j = [], n, m
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(out))

print(lcs("abcde", "ace"))
print(lcs("AGGTAB", "GXTXAYB"))
print(lcs("abc", "abc"))
print(lcs("abc", "def"))
print(lcs("", "abc"))
print(lcs_string("ABCBDAB", "BDCABA"))
p = "".join(chr(ord('a') + i * 7 % 26) for i in range(3000))
q = "".join(chr(ord('a') + i * 11 % 26) for i in range(3000))
print(lcs(p, q))
3
4
3
0
0
BCBA
1154

Three real bugs

Bug 1: forgetting the minus one. Row i is about the letter at index i - 1.

import java.util.*;

public class Main {
    static int lcs(String a, String b) {
        int n = a.length(), m = b.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i) == b.charAt(j))
                    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][m];
    }
    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace"));
    }
}
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: Index 3 out of bounds for length 3
    at Main.lcs(Main.java:9)
    at Main.main(Main.java:17)

j runs up to m = 3, but the last letter of "ace" is at index 2. Fix: a.charAt(i - 1) == b.charAt(j - 1).

Bug 2: writing 0 on a mismatch.

import java.util.*;

public class Main {
    static int lcs(String a, String b) {
        int n = a.length(), m = b.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = 0;
            }
        return dp[n][m];
    }
    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace"));
    }
}
1

1 instead of 3. Resetting to zero breaks the chain at every gap: that's the recurrence for the longest common substring (and even then the answer is the biggest cell, not the corner). Fix: Math.max(dp[i - 1][j], dp[i][j - 1]).

Bug 3: on a match, adding 1 to max(up, left) instead of the diagonal.

import java.util.*;

public class Main {
    static int lcs(String a, String b) {
        int n = a.length(), m = b.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1))
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        return dp[n][m];
    }
    public static void main(String[] args) {
        System.out.println(lcs("aa", "a"));
    }
}
2

2 instead of 1: the single a of "a" was matched with both as of "aa". The diagonal means both letters are used up together. Fix: dp[i - 1][j - 1] + 1.

Complexity

Approach Time Space Big input
Plain recursion O(2^(n + m)) O(n + m) stack 30 letters: Time Limit Exceeded
Top-down memo O(n × m) O(n × m) + O(n + m) stack 30 letters: 0 ms
DP table O(n × m) O(n × m) 3,000 × 3,000: ~73 ms
Walk back (letters / diff) + O(n + m) needs the full table
Two rows O(n × m) O(m) 10,000 × 10,000: ~280 ms

Tip: put the shorter string as b so the two rows are as short as possible: O(min(n, m)) space.

Common mistakes

Mistake What you see (real) Why Fix
a.charAt(i) == b.charAt(j) StringIndexOutOfBoundsException: Index 3 out of bounds for length 3 row i is letter i - 1 charAt(i - 1), charAt(j - 1)
Mismatch: dp[i][j] = 0 1 instead of 3 that's longest common substring max(up, left)
Match: max(up, left) + 1 2 instead of 1 for "aa", "a" a letter used twice dp[i-1][j-1] + 1
new int[n][m] ArrayIndexOutOfBoundsException prefixes are 0 … n and 0 … m (n + 1) × (m + 1)
Two rows, then trying to walk back wrong / impossible the old rows are gone keep the full table for reconstruction
Comparing lines with == lines never match == compares references a[i - 1].equals(b[j - 1])

Mini project: a mini diff tool

The diff program above is the mini project. Make it read two versions of a short text (one line each in two arrays, or split a paragraph with split("\n")) and print the + / - / kept lines. Extensions: print a summary like 2 deleted, 2 added, 4 kept; colour the output; compare word by word instead of line by line.

Practice

1. Delete Operation for Two Strings (LeetCode 583). Fewest deletions (from either string) to make them equal.

Solution

Keep the LCS, delete every other letter: n + m - 2 × LCS.

# Delete Operation for Two Strings (LeetCode 583): keep the LCS, delete everything else.
def min_distance(a, b):
    m = len(b)
    prev = [0] * (m + 1)
    for ch in a:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            cur[j] = prev[j - 1] + 1 if ch == b[j - 1] else max(prev[j], cur[j - 1])
        prev = cur
    return len(a) + len(b) - 2 * prev[m]

print(min_distance("sea", "eat"))
print(min_distance("leetcode", "etco"))
2
4

2. Uncrossed Lines (LeetCode 1035). Connect equal numbers of two arrays with lines that never cross. Most lines?

Solution

Lines that don't cross keep their order in both arrays: it's the LCS of two integer arrays.

# Uncrossed Lines (LeetCode 1035): lines may not cross, so the matched numbers keep their order: LCS.
def max_uncrossed_lines(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            dp[i][j] = dp[i - 1][j - 1] + 1 if a[i - 1] == b[j - 1] else max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

print(max_uncrossed_lines([1, 4, 2], [1, 2, 4]))
print(max_uncrossed_lines([2, 5, 1, 2, 5], [10, 5, 2, 1, 5, 2]))
2
3

3. Shortest Common Supersequence (LeetCode 1092). The shortest string that has both a and b as subsequences.

Solution

Its length is n + m - LCS (the common part is written once). Build it by walking the LCS table back, writing a matched letter once and an unmatched letter from whichever side you step.

# Shortest Common Supersequence (LeetCode 1092): walk the LCS table back, writing common letters once.
def shortest_common_supersequence(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            dp[i][j] = dp[i - 1][j - 1] + 1 if a[i - 1] == b[j - 1] else max(dp[i - 1][j], dp[i][j - 1])
    out, i, j = [], n, m
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            out.append(a[i - 1]); i -= 1
        else:
            out.append(b[j - 1]); j -= 1
    out.extend(reversed(a[:i])); out.extend(reversed(b[:j]))
    return "".join(reversed(out))

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

4. Longest Palindromic Subsequence (LeetCode 516).

Solution

A palindrome reads the same backwards, so it's a common subsequence of s and reverse(s).

# Longest Palindromic Subsequence (LeetCode 516): the LCS of s and its reverse.
def longest_palindrome_subseq(s):
    b = s[::-1]
    m = len(b)
    prev = [0] * (m + 1)
    for ch in s:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            cur[j] = prev[j - 1] + 1 if ch == b[j - 1] else max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

print(longest_palindrome_subseq("bbbab"))
print(longest_palindrome_subseq("cbbd"))
4
2

Quick quiz

a = "ABCBDAB", b = "BDCABA". LCS length? A) 3 B) 4 C) 5 D) 6

Answer

B) 4: for example BCBA (the walk back above prints it) or BDAB. No common subsequence of length 5 exists.

Interview questions

  1. Subsequence vs substring? Subsequence: gaps allowed, order kept. Substring: contiguous.
  2. State and recurrence? dp[i][j] over prefixes; match → dp[i-1][j-1] + 1, else max(dp[i-1][j], dp[i][j-1]); row 0 and column 0 = 0.
  3. Why is greedy (match the first equal letters) wrong? An early match can block a longer chain; only trying both "drop" choices is safe.
  4. How do you print the LCS, not just its length? Keep the full table and walk back from (n, m).
  5. Complexity? Can you save space? O(n × m) time; O(min(n, m)) space with two rows (length only).
  6. LCS vs longest common substring? Substring resets to 0 on a mismatch and takes the maximum cell anywhere.
  7. Where is LCS used? diff / version control, DNA and protein alignment, plagiarism checks, spell-check suggestions (with edit distance, next episode).

Glossary

Term Meaning
Subsequence Delete any letters, keep the order
Substring One contiguous piece
Common subsequence A subsequence of both strings
LCS Longest common subsequence
Prefix The first i letters; i = 0 is empty
State (i, j): first i of a, first j of b
Recurrence Match: diagonal + 1; else max(up, left)
Memoization Top-down recursion with a notebook
Tabulation Bottom-up table filling
Walk back Following the table back to recover the letters
Diff Kept, deleted (-) and added (+) lines between two versions
Rolling array Keeping two rows instead of the whole table

Summary

  • LCS: the longest sequence of letters (or lines) found in both inputs in the same order, gaps allowed.
  • The plain recursion is right but explodes: two 30-letter strings time out.
  • dp[i][j]: match → dp[i-1][j-1] + 1, else max(dp[i-1][j], dp[i][j-1]); answer dp[n][m].
  • Walk the table back for the letters; with lines instead of letters, that's a diff.
  • O(n × m) time; two rows give O(min(n, m)) space for the length. Next episode: edit distance, the same table with insert, delete and replace.