AntInLoop

Longest Common Subsequence (LCS)

Longest Common Subsequence finds the longest sequence of characters appearing in the same relative order (not necessarily contiguous) in two strings using 2D Dynamic Programming.

Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code

Longest Common Subsequence (LCS)

Given two sequences $A$ (length $n$) and $B$ (length $m$), the Longest Common Subsequence (LCS) is the longest sequence that appears as a subsequence in both $A$ and $B$ (characters need not be contiguous, only in the same relative order). LCS is the foundation of git diff, DNA sequence alignment, and Edit Distance.

At a Glance

| Property | Value |

| :--- | :--- |

| Time Complexity | $O(n \cdot m)$ |

| Auxiliary Space | $O(n \cdot m)$ (for reconstruction) / $O(\min(n, m))$ (length only) |

| State Definition | dp[i][j] = LCS length of prefixes A[0..i-1] and B[0..j-1] |

| Best Used When | Diffing text/files, bioinformatics alignment, string similarity, palindrome subsequences |

---

How It Works

For every $1 \le i \le n$ and $1 \le j \le m$:

$dp[i][j] = \begin{cases} dp[i - 1][j - 1] + 1 & \text{if } A[i - 1] = B[j - 1] \\ \max(dp[i - 1][j],\ dp[i][j - 1]) & \text{if } A[i - 1] \ne B[j - 1] \end{cases}$

Base cases: dp[0][j] = 0 and dp[i][0] = 0 (LCS with an empty string is 0).

procedure lcs(A, B):
    n = length(A), m = length(B)
    dp = (n + 1) x (m + 1) array of 0
    for i = 1 to n:
        for j = 1 to m:
            if A[i - 1] == B[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][m]

Step-by-Step Trace

A = "ABCDE", B = "ACE":

  • A[0]='A' == B[0]='A' → dp[1][1] = 1
  • A[2]='C' == B[1]='C' → dp[3][2] = dp[2][1] + 1 = 2
  • A[4]='E' == B[2]='E' → dp[5][3] = dp[4][2] + 1 = 3
  • Result: LCS length = 3 ("ACE").

---

Complexity & Key Insights

  • Space Optimization: Computing just the length only needs the previous row prev and current row cur, reducing memory from $O(nm)$ to $O(\min(n, m))$.
  • Reconstructing the Actual LCS: Walk backward from (n, m): if A[i - 1] == B[j - 1], append A[i - 1] and move diagonally (i - 1, j - 1); otherwise step toward whichever of dp[i - 1][j] or dp[i][j - 1] is larger. Reverse at the end.
  • Hidden LCS Problems:
  • Longest Palindromic Subsequence (LPS) of S = LCS(S, reverse(S)).
  • Shortest Common Supersequence (SCS) length = n + m - LCS(A, B).
  • Minimum Deletions to Make Two Strings Equal = n + m - 2 * LCS(A, B).

---

Practice Problems

Easy

1. Longest Common Subsequence Length (Space-Optimized, LeetCode 1143)

Return the length of the LCS of two strings text1 and text2 in $O(\min(n, m))$ space.

Approach: Roll two 1D rows prev and cur of length m + 1. Time: $O(nm)$. Space: $O(m)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int lcsLength(const std::string& a, const std::string& b) {
    int n = static_cast<int>(a.size()), m = static_cast<int>(b.size());
    std::vector<int> prev(m + 1, 0), cur(m + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i - 1] == b[j - 1]) cur[j] = prev[j - 1] + 1;
            else cur[j] = std::max(prev[j], cur[j - 1]);
        }
        prev.swap(cur);
    }
    return prev[m];
}

int main() {
    std::cout << lcsLength("abcde", "ace") << "\n"; // 3
    return 0;
}

</details>

2. Reconstruct the Actual LCS String

Return one actual Longest Common Subsequence string of a and b.

Approach: Fill the full (n + 1) x (m + 1) DP table, then backtrack from (n, m) to (0, 0) and reverse the collected characters. Time: $O(nm)$. Space: $O(nm)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

std::string buildLCS(const std::string& a, const std::string& b) {
    int n = static_cast<int>(a.size()), m = static_cast<int>(b.size());
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i - 1] == b[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 res;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            res.push_back(a[i - 1]);
            --i; --j;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            --i;
        } else {
            --j;
        }
    }
    std::reverse(res.begin(), res.end());
    return res;
}

int main() {
    std::cout << buildLCS("AGGTAB", "GXTXAYB") << "\n"; // GTAB
    return 0;
}

</details>

---

Intermediate

3. Longest Palindromic Subsequence (LeetCode 516)

Given a string s, find the length of its longest palindromic subsequence.

Approach: A palindrome reads the same forward and backward, so LPS(s) = LCS(s, reverse(s)). Time: $O(n^2)$. Space: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int longestPalindromeSubseq(const std::string& s) {
    std::string rev(s.rbegin(), s.rend());
    int n = static_cast<int>(s.size());
    std::vector<int> prev(n + 1, 0), cur(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s[i - 1] == rev[j - 1]) cur[j] = prev[j - 1] + 1;
            else cur[j] = std::max(prev[j], cur[j - 1]);
        }
        prev.swap(cur);
    }
    return prev[n];
}

int main() {
    std::cout << longestPalindromeSubseq("bbbab") << "\n"; // 4 ("bbbb")
    return 0;
}

</details>

4. Shortest Common Supersequence (LeetCode 1092)

Given two strings a and b, return the shortest string that has both a and b as subsequences.

Approach: Compute the LCS table and backtrack from (n, m). Whenever a[i - 1] == b[j - 1], emit the shared character once; otherwise emit the character from whichever side we step away from. Finally append any remaining prefix of a or b and reverse. Time: $O(nm)$. Space: $O(nm)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

std::string shortestCommonSupersequence(const std::string& a, const std::string& b) {
    int n = static_cast<int>(a.size()), m = static_cast<int>(b.size());
    std::vector<std::vector<int>> dp(n + 1, std::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 : std::max(dp[i - 1][j], dp[i][j - 1]);

    std::string res;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) { res.push_back(a[i - 1]); --i; --j; }
        else if (dp[i - 1][j] >= dp[i][j - 1]) { res.push_back(a[i - 1]); --i; }
        else { res.push_back(b[j - 1]); --j; }
    }
    while (i > 0) res.push_back(a[--i]);
    while (j > 0) res.push_back(b[--j]);
    std::reverse(res.begin(), res.end());
    return res;
}

int main() {
    std::cout << shortestCommonSupersequence("abac", "cab") << "\n"; // cabac
    return 0;
}

</details>

---

Hard

5. LCS of Two Permutations in $O(n \log n)$

Given two permutations A and B of $\{1, 2, \dots, n\}$ (with $n \le 2 \times 10^5$), find their LCS length in $O(n \log n)$ time!

Approach: Because every value appears once in each permutation, map each value v to its position pos[v] in A. Then a common subsequence of A and B corresponds to a strictly increasing sequence of pos[B[i]]—reducing LCS to $O(n \log n)$ Longest Increasing Subsequence (LIS)!

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <vector>

int lcsPermutations(const std::vector<int>& A, const std::vector<int>& B) {
    int n = static_cast<int>(A.size());
    std::vector<int> pos(n + 1);
    for (int i = 0; i < n; ++i) pos[A[i]] = i;

    std::vector<int> tails;
    for (int x : B) {
        int idx = pos[x];
        auto it = std::lower_bound(tails.begin(), tails.end(), idx);
        if (it == tails.end()) tails.push_back(idx);
        else *it = idx;
    }
    return static_cast<int>(tails.size());
}

int main() {
    std::cout << lcsPermutations({3, 2, 1, 4, 5}, {1, 2, 3, 4, 5}) << "\n"; // 3 (e.g. 1,4,5)
    return 0;
}

</details>

---

Related Algorithms