Find the longest common subsequence length
Find the length of the longest sequence of characters that appears in two strings in the same order, not necessarily contiguously.
Course progress
Problem 92 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
first = "AGGTAB"; second = "GXTXAYB"
Expected output
4
What is happening?
GTAB appears in both strings in the same order. It has length 4, and no longer common subsequence exists.
Solution strategy
Build the right mental model
Build answers for every prefix pair. Matching final characters extend the diagonal state; otherwise keep the better state after dropping one character.
Core concepts
dynamic programming · strings
Complexity
Time O(n x m), space O(n x m).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for longest-common-subsequence
using System;
class Program
{
static int LongestCommonSubsequence(string first, string second)
{
int[,] lengths = new int[first.Length + 1, second.Length + 1];
for (int i = 1; i <= first.Length; i++)
for (int j = 1; j <= second.Length; j++)
lengths[i, j] = first[i - 1] == second[j - 1]
? lengths[i - 1, j - 1] + 1
: Math.Max(lengths[i - 1, j], lengths[i, j - 1]);
return lengths[first.Length, second.Length];
}
static void Main()
{
Console.WriteLine(LongestCommonSubsequence("AGGTAB", "GXTXAYB"));
}
}Knowledge check
Questions students often ask
What is the main idea behind find the longest common subsequence length?
Build answers for every prefix pair. Matching final characters extend the diagonal state; otherwise keep the better state after dropping one character.
What is the time and space complexity of this solution?
Time O(n x m), space O(n x m).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.