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.

The mental model is this: define one state as a smaller question whose answer can help build larger answers. That picture matters because it tells the student what information is available immediately and what must be searched, stored, or recomputed.

The core invariant is that when a state is used, every smaller state it depends on must already be correct or memoized. If a solution cannot state that rule, the code may still run on a sample input but fail on edge cases.

A strong implementation usually uses state definitions, recurrence formulas, base cases, table order, memoization maps, and reconstruction when needed. The goal is not just to memorize an API; the goal is to know why each operation is allowed and what it costs.

In competitive programming, Longest Common Subsequence tends to appear when the problem asks for best, count, longest, shortest, ways, or choices over prefixes, positions, capacities, or subsets. Spotting that signal is often the difference between a nested-loop solution and an efficient one.

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

Use a tiny input and focus on two-dimensional dp state. The goal is to see how the topic changes state before scaling it to a full problem.

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

Turn the topic into usable problem-solving skill

Students can use this page before a lesson, after a difficult homework assignment, or while preparing for AP Computer Science A extensions, Advanced Topics in CS, USACO growth, or a college data structures course.

Schedule Free Consultation Text Us Open Online Compiler