Advanced Algorithm Design · Dynamic Programming

Longest Common Subsequence

Longest common subsequence is a classic DP problem that compares two sequences while allowing skipped characters.

Enroll Now Text Us Contact Code Scholars Full DSA Course

Student Focus

This topic helps students practice DP tables with a visual, concrete problem.

Guided Lesson Notes

Understanding Longest Common Subsequence

Longest Common Subsequence focuses on overlapping subproblems, reusable answers, and turning recursion into a table or memo. Longest common subsequence is a classic DP problem that compares two sequences while allowing skipped characters.

Model: define one state as a smaller question whose answer can help build larger answers.

Invariant: when a state is used, every smaller state it depends on must already be correct or memoized.

Implementation: state definitions, recurrence formulas, base cases, table order, memoization maps, and reconstruction when needed.

Use Longest Common Subsequence when the problem asks for best, count, longest, shortest, ways, or choices over prefixes, positions, capacities, or subsets.

Visual Model

A small picture for Longest Common Subsequence

0123012301230123012301230

Key Ideas

Two-dimensional DP state
Match versus skip choices
Table reconstruction

Practice Prompts

Fill an LCS table for two short strings.
Recover one valid subsequence from the completed table.

Vocabulary

Terms students should be able to say clearly

State

A smaller subproblem described by indexes, capacity, mask, or other parameters.

Recurrence

The formula that builds one state from smaller states.

Base case

A state whose answer is known immediately.

Memoization

Top-down caching of recursive answers.

Tabulation

Bottom-up filling of a table.

Transition

One possible move from previous states into the current state.

Worked Example

Worked example: tracing Longest Common Subsequence

Trace a small input, focusing on two-dimensional dp state.

1Write a small input where Longest Common Subsequence is clearly useful.
2Label the part of the input related to Two-dimensional DP state.
3Perform one operation and explain which invariant is still true afterward.
4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

Operation	Typical Cost	Reason
Trace a small input	Small n	Use a tiny example to understand state changes before coding.
Implement the core idea	Depends on topic	Choose data structures that match the operations you need.
Analyze growth	Big-O	Explain how work changes as the input gets larger.

Common Mistakes

What to watch while practicing

Coding before drawing the structure or state changes.
Forgetting the invariant that makes the algorithm correct.
Testing only the sample input and skipping boundary cases.
Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Longest Common Subsequence interview problem: Minimum Deletions to Make Strings Equal

Interview medium

Problem

Given two strings, find the minimum number of character deletions needed so the remaining strings are equal.

Input

The first line contains word1. The second line contains word2.

Output

Print the minimum number of deletions.

Sample Input

sea
eat

Sample Output

Why the sample works

Deleting s from sea and t from eat leaves ea in both strings.

Approach

1Find the longest common subsequence length.
2Characters in the LCS can remain in both strings.
3Every other character must be deleted from one of the strings.
4The answer is len(a) + len(b) - 2 * LCS.

O(nm) time and O(nm) extra space.

Java Solution

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String a = sc.nextLine().trim();
    String b = sc.nextLine().trim();

    int n = a.length();
    int 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]);
        }
      }
    }

    int lcs = dp[n][m];
    System.out.println(n + m - 2 * lcs);
  }
}

Python Solution

a = input().strip()
b = input().strip()

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):
        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])

lcs = dp[n][m]
print(n + m - 2 * lcs)

Practice Challenge

Make the idea your own

Create a two-minute explanation of Longest Common Subsequence: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free Session Text Us Open Online Compiler