1143. Longest Common Subsequence

At a Glance

Topic: dp-2d
Pattern: Dynamic Programming (2D string/table LCS)
Difficulty: Medium
Companies: Amazon, Google, Facebook, Microsoft, Bloomberg
Frequency: Very High
LeetCode: 1143

Problem (one-liner)

Given strings text1 and text2, return the length of their longest common subsequence (relative order preserved, not necessarily contiguous). Input: two strings. Output: non-negative length.

Recognition Cues

“Longest common subsequence”
O(m*n) table: compare characters at two indices
If characters match, extend from diagonal; else max of up/left

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — 3^(m+n) backtracking.
Better — full 2D length table — O(m*n) time / O(m*n) space.
Optimal — 1D rolling on shorter dimension — O(m*n) time / O(min(m,n)) space. <- pick this in interview.

Optimal Solution

Go

package main

func longestCommonSubsequenceTable(text1 string, text2 string) int {
	rows := len(text1)
	cols := len(text2)
	table := make([][]int, rows+1)
	for row := range table {
		table[row] = make([]int, cols+1)
	}
	for row := 1; row <= rows; row++ {
		for col := 1; col <= cols; col++ {
			if text1[row-1] == text2[col-1] {
				table[row][col] = table[row-1][col-1] + 1
			} else {
				left := table[row-1][col]
				up := table[row][col-1]
				if left > up {
					table[row][col] = left
				} else {
					table[row][col] = up
				}
			}
		}
	}
	return table[rows][cols]
}

func longestCommonSubsequence(text1 string, text2 string) int {
	rows := len(text1)
	cols := len(text2)
	if rows < cols {
		return longestCommonSubsequence(text2, text1)
	}
	dp := make([]int, cols+1)
	for row := 1; row <= rows; row++ {
		diagonal := 0
		for col := 1; col <= cols; col++ {
			up := dp[col]
			if text1[row-1] == text2[col-1] {
				dp[col] = diagonal + 1
			} else {
				if up < dp[col-1] {
					dp[col] = dp[col-1]
				}
			}
			diagonal = up
		}
	}
	return dp[cols]
}

JavaScript

function longestCommonSubsequenceTable(text1, text2) {
	const rows = text1.length;
	const cols = text2.length;
	const table = Array.from({ length: rows + 1 }, () =>
		new Array(cols + 1).fill(0)
	);
	for (let row = 1; row <= rows; row++) {
		for (let col = 1; col <= cols; col++) {
			if (text1[row - 1] === text2[col - 1]) {
				table[row][col] = table[row - 1][col - 1] + 1;
			} else {
				table[row][col] = Math.max(
					table[row - 1][col],
					table[row][col - 1]
				);
			}
		}
	}
	return table[rows][cols];
}

function longestCommonSubsequence(text1, text2) {
	const rows = text1.length;
	const cols = text2.length;
	const dp = new Array(cols + 1).fill(0);
	for (let row = 1; row <= rows; row++) {
		let diagonal = 0;
		for (let col = 1; col <= cols; col++) {
			const up = dp[col];
			if (text1[row - 1] === text2[col - 1]) {
				dp[col] = diagonal + 1;
			} else {
				dp[col] = Math.max(up, dp[col - 1]);
			}
			diagonal = up;
		}
	}
	return dp[cols];
}