Dynamic Programming on Strings: Longest Common Subsequence (LCS)

Welcome to the foundational chapter of Dynamic Programming on Strings. String-based DP problems typically revolve around comparisons, replacements, edits, and matching patterns. Mastering this problem will unlock your ability to solve almost any advanced string-based dynamic programming challenge.

1. Why Do We Need DP on Strings? (Problem Statement)

When dealing with strings, standard linear scans or brute-force approaches fail because of combinatorial explosions.

• The Status Quo Challenge: Given two strings, $S_1$ and $S_2$, how do we find the longest sequence of characters that appear in both strings in the same relative order (not necessarily contiguous)?
• Real-World Applications: DNA sequence alignment (bioinformatics), diff utilities in version control systems (like Git), plagiarism detection, and spell checkers.

2. Core Mental Model & The Terminology of Subsequences

Before writing code, we must precisely define what a subsequence is.

What is a Subsequence?

A subsequence is formed by deleting zero or more characters from a string without changing the relative order of the remaining characters.

• For string s = "abc":
  • Consecutive subsequences: "ab", "bc", "abc"
  • Non-consecutive subsequences: "ac"
  • Single characters: "a", "b", "c"
  • Empty string: "" (always a valid subsequence)

Formula: For a string of length $n$, the total number of possible subsequences is $2^n$ (since each character has two choices: either pick it or don't pick it).

What is the Longest Common Subsequence (LCS)?

Given two strings:

• String 1: s1 = "acd"
• String 2: s2 = "ced"

If we list all $2^3 = 8$ subsequences for both and compare them, we look for the longest sequence present in both sets. Here, "cd" is common to both and has a length of 2.

3. Naive Brute Force Approach vs. The Limitation

• Brute Force Strategy: Generate all $2^n$ subsequences for String 1 and all $2^m$ subsequences for String 2, store them, and perform a linear comparison to find the longest match.
• Time Complexity: $\mathcal{O}(2^n + 2^m)$, which is exponential and completely impractical for strings of moderate length (e.g., length $\ge 30$).
• The Better Path: Instead of generating all subsequences explicitly and comparing them, we can use recursion with pointers/indices to explore choices dynamically.

4. Step-by-Step Evolution: Formulating the Recursion

To solve string comparison problems recursively, we follow three golden rules of dynamic programming:

1. Express everything in terms of indexes.
2. Explore all possibilities on that index.
3. Take the best among them (since we want the longest common subsequence).

Rule 1: Expressing via Two Indexes

Because we are comparing two strings simultaneously, a single index cannot represent the state of both strings. We need two pointers:

• index1 representing the substring of $S_1$ from index 0 to index1.
• index2 representing the substring of $S_2$ from index 0 to index2.

Let $f(i, j)$ represent the length of the Longest Common Subsequence of $S_1[0 \dots i]$ and $S_2[0 \dots j]$.

Rule 2 & 3: Exploring Possibilities (Match vs. Non-Match)

When comparing characters at $S_1[i]$ and $S_2[j]$, we encounter two scenarios:

Case A: Characters Match ($S_1[i] == S_2[j]$)

If the characters match, we have successfully found 1 character belonging to our LCS. We add 1 to our answer and shrink both strings by decrementing both indices.

Recurrence: 1 + f(i - 1, j - 1)

Case B: Characters Do Not Match ($S_1[i] \neq S_2[j]$)

If the characters do not match, the current characters cannot be part of the same optimal LCS together. Therefore, we must explore two possibilities:

1. Keep $S_1[i]$ fixed and decrement $j$: f(i, j - 1)
2. Keep $S_2[j]$ fixed and decrement $i$: f(i - 1, j)

Since we want the longest common subsequence, we take the maximum of these two branching choices.

Recurrence: max(f(i - 1, j), f(i, j - 1))

5. Complete Recursive Implementation & Base Cases

Identifying Base Cases

When do our recursive pointer indices stop? When one of the strings is exhausted (i.e., an index drops below 0).

• If i < 0 or j < 0, no characters are left to compare, so the longest common subsequence length is 0.

Pure Recursive Code (Mental Blueprint)

int lcsUtil(string &s1, string &s2, int i, int j) {
    // Base Case: If either string is exhausted
    if (i < 0 || j < 0) return 0;
    
    // Match Case
    if (s1[i] == s2[j]) {
        return 1 + lcsUtil(s1, s2, i - 1, j - 1);
    }
    
    // Non-Match Case: Try shrinking either s1 or s2 and take the max
    return max(lcsUtil(s1, s2, i - 1, j), lcsUtil(s1, s2, i, j - 1));
}

int longestCommonSubsequence(string text1, string text2) {
    int n = text1.size();
    int m = text2.size();
    return lcsUtil(text1, text2, n - 1, m - 1);
}

6. Overlapping Subproblems & Memoization (Top-Down DP)

Why Memoization?

Drawing the recursion tree reveals that identical states (e.g., f(i, j)) are computed multiple times. By storing computed results in a 2D DP table initialized to -1, we avoid redundant calculations.

Memoized Code (Top-Down)

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

class Solution {
private:
    int lcsMemo(int i, int j, string &s1, string &s2, vector<vector<int>> &dp) {
        // Base Case
        if (i < 0 || j < 0) return 0;
        
        // Return cached result if already computed
        if (dp[i][j] != -1) return dp[i][j];
        
        // Match
        if (s1[i] == s2[j]) {
            return dp[i][j] = 1 + lcsMemo(i - 1, j - 1, s1, s2, dp);
        }
        
        // Non-Match
        return dp[i][j] = max(lcsMemo(i - 1, j, s1, s2, dp), lcsMemo(i, j - 1, s1, s2, dp));
    }

public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size();
        int m = text2.size();
        vector<vector<int>> dp(n, vector<int>(m, -1));
        return lcsMemo(n - 1, m - 1, text1, text2, dp);
    }
};

• Time Complexity: $\mathcal{O}(n \times m)$ — Each state is computed only once.
• Space Complexity: $\mathcal{O}(n \times m)$ for the DP table $+\mathcal{O}(n + m)$ for the auxiliary recursion stack space.

7. Transitioning to Tabulation (Bottom-Up DP) & Index Shifting

To eliminate auxiliary stack space and avoid recursion overhead, we convert our solution into an iterative Bottom-Up approach.

The Challenge with Tabulation and Negative Indices

In our recursive code, base cases occur when i < 0 or j < 0. However, a standard array/vector cannot have a negative index like dp[-1][-1].

The Solution: Right Shift Indexing

We shift all indices by 1 unit to the right:

• Original Index -1 $\rightarrow$ Shifted Index 0
• Original Index 0 $\rightarrow$ Shifted Index 1
• Original Index n - 1 $\rightarrow$ Shifted Index n

Note Rule Transformation:

• Every time we check or reference string characters using shifted DP indices, we access s1[i - 1] and s2[j - 1].
• The DP table size becomes (n + 1) \times (m + 1).

Tabulation Algorithm Steps

1. Copy the Base Cases: Initialize row 0 and column 0 of the DP table to 0 (representing exhausted strings).
2. Write Opposite Loops: Loop i from 1 to n and j from 1 to m.
3. Copy the Recurrence: Translate recursive logic into iterative table lookups.

Tabulated Code (Bottom-Up)

class Solution {
public:
    int longestCommonSubsequence(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();
        
        // DP table of size (n + 1) x (m + 1) with 0-initialization
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        
        // Base cases are implicitly handled since dp[0][j] and dp[i][0] are 0.
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // Match case (using i-1 and j-1 for actual string characters)
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } 
                // Non-match case
                else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[n][m];
    }
};

8. Ultimate Space Optimization

If you examine the tabulation recurrence:

This means we do not need to store the entire $n \times m$ matrix. We only need two rows:

1. previous: representing row i - 1
2. curr: representing row i

Space-Optimized Code

class Solution {
public:
    int longestCommonSubsequence(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();
        
        vector<int> previous(m + 1, 0), curr(m + 1, 0);
        
        // Base cases for row 0 are already 0 in 'previous' vector
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    curr[j] = 1 + previous[j - 1];
                } else {
                    curr[j] = max(previous[j], curr[j - 1]);
                }
            }
            // Move current row to previous for the next iteration
            previous = curr;
        }
        
        return previous[m];
    }
};

• Time Complexity: $\mathcal{O}(n \times m)$
• Space Complexity: $\mathcal{O}(m)$ — Drastically reduced by keeping only a single previous row in memory!

9. Approach Comparison Summary

10. Summary and Key Takeaways

• Subsequence Definition: Order matters, but characters do not need to be contiguous in the string.
• Index Representation: Comparing two strings requires a two-parameter state f(i, j).
• The Core Dichotomy: String DP problems typically break down into two fundamental checks: Match (add 1, shrink both pointers) vs. Non-Match (branch, shrink one pointer at a time, and take the max).
• Index Shifting Trick: Shifting indices by +1 in Tabulation elegantly circumvents negative boundary checks without writing messy conditional base-case logic.
• Space Reduction Principle: Whenever a DP state depends only on the immediate previous row (i - 1), you can optimize space complexity down from $\mathcal{O}(n \times m)$ to $\mathcal{O}(m)$ using rolling vectors.