Abstract / Summary

Find the length of the longest sequence that appears in the same order in both given strings.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 59% (3+ million submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the length of the longest common subsequence (LCS) between two input strings. It follows a classic dynamic-programming approach, constructing a two-dimensional table where each cell records the LCS length for the prefixes of the strings processed so far. The algorithm iterates over the characters of both strings, updating the table based on character equality, and finally returns the value stored in the bottom-right cell, which represents the LCS length for the complete strings.

Key Steps

The first step determines the dimensions of the DP table. The width corresponds to the length of the first string, while the height corresponds to the length of the second string.

auto width  = text1.size();
auto height = text2.size();

A table named ops is allocated as a vector of vectors of short. The outer vector has width + 1 rows, and each inner vector is resized to height + 1 columns, all initialized to zero. Using short reduces the memory footprint compared with a larger integer type, which is beneficial when the strings are long but the LCS length remains within the range of a 16-bit signed integer.

vector<vector<short>> ops(width + 1);
for (auto& o : ops)
    o.resize(height + 1, 0);

The core of the algorithm consists of a double loop that traverses every character pair (i, j). For each pair, the code checks whether the characters match. If they do, the value in the diagonal predecessor cell ops[i][j] is incremented by one and stored in ops[i+1][j+1]. This reflects the extension of a common subsequence by the matching character.

for (int i = 0; i < width; i++)
    for (int j = 0; j < height; j++)
        if (text1[i] == text2[j])
            ops[i+1][j+1] = ops[i][j] + 1;

If the characters differ, the algorithm selects the larger of the two neighboring cells-either the left cell ops[i+1][j] or the upper cell ops[i][j+1]. This choice propagates the best LCS length found so far for the respective prefixes.

        else
            ops[i+1][j+1] = max(ops[i+1][j], ops[i][j+1]);

After the table is fully populated, the result is retrieved from the cell that corresponds to the full lengths of both strings.

return ops[width][height];

Edge Cases

The implementation gracefully handles empty input strings. When either text1 or text2 is empty, the corresponding dimension (width or height) becomes zero. The DP table is still created with an extra row and column of zeros, and the double loop does not execute because its bounds are zero. Consequently, the final return statement yields ops[0][height] or ops[width][0], both of which are zero, correctly indicating that no common subsequence exists.

When both strings consist of a single character, the loops iterate once. If the characters match, the diagonal cell receives a value of one; otherwise, the maximum of the adjacent zeros remains zero. This behavior correctly distinguishes the case of a single-character match from a mismatch.

The use of short for the DP table implicitly caps the maximum LCS length at 32,767. For typical problem constraints where input strings are not excessively long, this limit is sufficient, and the code still produces correct results without overflow.

Performance Optimizations

Memory usage is reduced by selecting short as the element type for the DP matrix. This choice halves the memory consumption relative to a default int on most platforms, allowing larger inputs to be processed within the same memory budget.

The table is allocated with an extra row and column, eliminating the need for boundary checks inside the nested loops. By always accessing ops[i+1][j+1], the algorithm avoids conditional statements that would otherwise be required to handle the first row and column, thereby streamlining the inner loop body.

The inner loop body consists of a single conditional and either an addition or a max operation. Both operations are inexpensive and benefit from modern CPU pipelines and branch prediction, contributing to a tight and efficient execution path.

Finally, the algorithm accesses the DP table in row-major order, which aligns with the underlying memory layout of vector<vector<short>>. This access pattern promotes cache locality, as consecutive iterations of the inner loop read and write adjacent memory locations, reducing cache miss penalties.

Imagine two long ribbons covered in colorful blocks. Each block has a letter on it. The goal is to find the longest path of blocks that appears on both ribbons in the exact same order. Because it is hard to check every single combination, the code uses a big sheet of graph paper.

Think of this paper as a giant grid. Each square on the grid represents a little piece of the work. As the code walks across the ribbons, it looks at two blocks at a time. If the blocks match, it marks the square to say that the secret chain just got one block longer. If the blocks do not match, it looks at the squares right above and to the left to see which one already has the biggest number. It copies that number to keep the best progress found so far. By the time the code reaches the very last square on the bottom right of the paper, that square holds the magic number representing the longest chain of matching letters found between the two ribbons.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java							TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#	JS		Go		Rust	TS
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	begeekmyfriend								C
	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	everthis					JS
	FelixFan1122				C#
	fpdjsns	C++
	fsq	C++
	halfrost							Go
	JoshCrozier					JS
	keineahnung2345	C++
	lkwq007		Python
	MacJim	C++
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	wisdompeak	C++
	yuanliu666						Kotlin
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
FelixFan1122	C#
fpdjsns	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
MacJim	C++
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++
yuanliu666	Kotlin

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality