Problem Statement
Given two strings firstText and secondText, return the length of the longest character sequence appearing in both strings in the same relative order.
A subsequence may delete zero or more characters without changing the order of the remaining characters. Consecutive positions are not required. An empty common subsequence has length 0.
Example 1
Input: firstText = "abcde", secondText = "ace"
Output: 3
Explanation: Characters "a", "c", and "e" appear in order inside both strings, so "ace" forms a longest common subsequence.
Example 2
Input: firstText = "abc", secondText = "def"
Output: 0
Explanation: No matching character exists across the two strings, so only the empty common subsequence remains.
Recursion
A comparison at two string positions gives a simple choice. Matching characters can join the common subsequence, so both positions move forward together. Different characters cannot join as a pair, so one position must move forward while the other position stays available.
The state solve(firstIndex, secondIndex) stores the best common subsequence length across the two remaining suffixes. The first call starts at solve(0, 0) because both complete strings must remain available.
Algorithm
Begin with
firstIndex = 0andsecondIndex = 0, so both complete strings remain available for the first comparison.Stop with length
0after either index reaches a string end, because an empty suffix cannot add another common character.Compare the current characters, because equality decides whether one common character can extend the answer immediately.
Move both indices forward and add
1after a match, because the matched pair becomes part of the common subsequence.Explore a branch skipping the first character after a mismatch, so the second character remains available for a later match.
Explore a branch skipping the second character after a mismatch, so the first character remains available for a later match.
Return the larger mismatch branch, because the longer valid common subsequence must be preserved.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Finds the best length across two suffixes. int solve( int firstIndex, int secondIndex, string& firstText, string& secondText ) { int firstLength = firstText.size(); int secondLength = secondText.size(); // An empty suffix cannot add a common character. if ( firstIndex == firstLength || secondIndex == secondLength ) { return 0; } // A match extends the answer from both next positions. if ( firstText[firstIndex] == secondText[secondIndex] ) { // Both matched positions become unavailable. return 1 + solve( firstIndex + 1, secondIndex + 1, firstText, secondText ); } // Skipping from the first string keeps the second. int skipFirst = solve( firstIndex + 1, secondIndex, firstText, secondText ); // Skipping from the second string keeps the first. int skipSecond = solve( firstIndex, secondIndex + 1, firstText, secondText ); // The longer skip branch gives the best length. return max(skipFirst, skipSecond); }public: // Returns the longest common subsequence length. int longestCommonSubsequence( string firstText, string secondText ) { // Both complete strings begin at position zero. return solve(0, 0, firstText, secondText); }};// Driver codeint main() { string firstText = "abcde"; string secondText = "ace"; Solution obj; cout << obj.longestCommonSubsequence( firstText, secondText ) << endl; return 0;}Complexity Analysis
Time Complexity: O(2(M + N)), where M and N are the lengths of the two strings, because a mismatch can create two recursive branches across a recursion depth bounded by the combined string lengths M + N.
Space Complexity: O(M + N), because the recursion stack can hold at most one call for every position advanced across both strings.
Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.
Memoization
Direct recursion reaches the same pair of suffix positions through many skip orders. Each position pair always produces the same best length, so repeated exploration adds cost without adding new information.
A two-dimensional dp array stores each solved state. A stored value replaces the repeated subtree with one lookup, while the recursive choices and state meaning stay unchanged.
Algorithm
Begin with the recursive state
solve(firstIndex, secondIndex), because the two suffix positions still describe every remaining choice.Create a
dptable filled with-1, so every untouched cell clearly marks an unsolved position pair.Stop with length
0after either suffix becomes empty, because no additional common character remains.Return
dp[firstIndex][secondIndex]after a stored value appears, because the matching state has already explored every useful choice.Store
1plus the diagonal state after matching characters, because both matched positions join the common subsequence.Store the larger one-position skip result after different characters, because only one current character can be discarded at a time.
Return the value from
solve(0, 0), because the starting state represents both complete strings.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Finds the best cached length across two suffixes. int solve( int firstIndex, int secondIndex, string& firstText, string& secondText, vector<vector<int>>& dp ) { int firstLength = firstText.size(); int secondLength = secondText.size(); // An empty suffix cannot add a common character. if ( firstIndex == firstLength || secondIndex == secondLength ) { return 0; } // A solved position pair can be reused directly. if (dp[firstIndex][secondIndex] != -1) { return dp[firstIndex][secondIndex]; } // A match extends the answer from both next positions. if ( firstText[firstIndex] == secondText[secondIndex] ) { // The diagonal result completes the matched state. dp[firstIndex][secondIndex] = 1 + solve( firstIndex + 1, secondIndex + 1, firstText, secondText, dp ); return dp[firstIndex][secondIndex]; } // Skipping from the first string keeps the second. int skipFirst = solve( firstIndex + 1, secondIndex, firstText, secondText, dp ); // Skipping from the second string keeps the first. int skipSecond = solve( firstIndex, secondIndex + 1, firstText, secondText, dp ); // The larger skip result completes the state. dp[firstIndex][secondIndex] = max( skipFirst, skipSecond ); return dp[firstIndex][secondIndex]; }public: // Returns the longest common subsequence length. int longestCommonSubsequence( string firstText, string secondText ) { int firstLength = firstText.size(); int secondLength = secondText.size(); // A minus one value marks every unsolved state. vector<vector<int>> dp( firstLength, vector<int>(secondLength, -1) ); // Both complete strings begin at position zero. return solve( 0, 0, firstText, secondText, dp ); }};// Driver codeint main() { string firstText = "abcde"; string secondText = "ace"; Solution obj; cout << obj.longestCommonSubsequence( firstText, secondText ) << endl; return 0;}Complexity Analysis
Time Complexity: O(M × N), where M and N are the lengths of the two strings, because at most M × N suffix pairs are solved once, with constant work per transition.
Space Complexity: O(M × N + M + N), because the dp table stores all position pairs, while the recursion stack can grow up to the combined lengths of the two strings.
Tabulation
Memoization calculates suffix states only after recursive calls request smaller suffixes. Tabulation removes the call stack by filling the same states in a deliberate reverse order.
An extra bottom row and right column represent empty suffixes with length 0. Moving upward and leftward guarantees availability of every finished diagonal, lower, and right neighbor.
Algorithm
Create a
(m + 1) x (n + 1)dptable filled with0, so the extra row and column directly represent empty suffixes.Process first-string positions from right to left, because every state depends on a later first-string position.
Process second-string positions from right to left, because the right neighbor must already hold the matching skip result.
Store
1 + dp[firstIndex + 1][secondIndex + 1]after equal characters, because the matched pair extends the diagonal suffix answer.Compare
dp[firstIndex + 1][secondIndex]withdp[firstIndex][secondIndex + 1]after different characters, because either current character may be skipped.Store the larger skip value, so the best common subsequence across the current suffix pair survives.
Return
dp[0][0], because the top-left state represents both complete strings.
Dry Run
lcs-tabulation-explicit-dp-states-v3.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the longest common subsequence length. int longestCommonSubsequence( string firstText, string secondText ) { int firstLength = firstText.size(); int secondLength = secondText.size(); // Extra boundaries represent empty suffixes. vector<vector<int>> dp( firstLength + 1, vector<int>(secondLength + 1, 0) ); // Reverse order keeps the lower row available. for ( int firstIndex = firstLength - 1; firstIndex >= 0; firstIndex-- ) { // Reverse order keeps the right cell available. for ( int secondIndex = secondLength - 1; secondIndex >= 0; secondIndex-- ) { // A match extends the diagonal suffix result. if ( firstText[firstIndex] == secondText[secondIndex] ) { dp[firstIndex][secondIndex] = 1 + dp[firstIndex + 1] [secondIndex + 1]; } else { // A mismatch keeps the better skip. dp[firstIndex][secondIndex] = max( dp[firstIndex + 1][secondIndex], dp[firstIndex][secondIndex + 1] ); } } } // The top-left state covers both full strings. return dp[0][0]; }};// Driver codeint main() { string firstText = "abcde"; string secondText = "ace"; Solution obj; cout << obj.longestCommonSubsequence( firstText, secondText ) << endl; return 0;}Complexity Analysis
Time Complexity: O(M × N), where M and N are the lengths of the two strings, because every pair of character positions fills one table cell with constant work.
Space Complexity: O(M × N), because the two-dimensional dp table stores one answer for every pair of suffix positions, with no recursion stack.
Space Optimization
Every tabulation state reads only the next row and the already completed part of the current row. Older rows never contribute again, so the full table carries more history than the transition needs.
Two one-dimensional rows preserve all required values. The shorter string becomes the column string, keeping row storage at the smaller input length without changing the LCS answer.
Algorithm
Place the shorter string along the row columns, because two rows of the smaller width minimize auxiliary storage.
Create
nextRowwith zeros, so every value initially represents an empty suffix from the other string.Process row-string positions from right to left, because every current state needs the completed next row.
Create a fresh zero-filled
currentRowfor each row position, so the empty column boundary remains available.Process column positions from right to left, because
currentRow[columnIndex + 1]must be ready before a mismatch.Calculate a match from
1 + nextRow[columnIndex + 1]or a mismatch from the larger skip value, preserving the tabulation transition.Shift
currentRowintonextRowafter a full row, because only the newest completed row can serve the next iteration.Return
nextRow[0], because the final retained row represents both complete strings.
Dry Run
lcs-space-optimization-explicit-dp-states-v2.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the longest common subsequence length. int longestCommonSubsequence( string firstText, string secondText ) { // The shorter string keeps row storage smaller. if (firstText.size() < secondText.size()) { swap(firstText, secondText); } int rowLength = firstText.size(); int columnLength = secondText.size(); // The next row begins as an empty suffix. vector<int> nextRow(columnLength + 1, 0); // Reverse order keeps the next row available. for ( int rowIndex = rowLength - 1; rowIndex >= 0; rowIndex-- ) { // A fresh row preserves the empty boundary. vector<int> currentRow(columnLength + 1, 0); // Reverse order keeps the right value available. for ( int columnIndex = columnLength - 1; columnIndex >= 0; columnIndex-- ) { // The current value follows match or skip rules. if ( firstText[rowIndex] == secondText[columnIndex] ) { currentRow[columnIndex] = 1 + nextRow[columnIndex + 1]; } else { // A mismatch keeps the better skip. currentRow[columnIndex] = max( nextRow[columnIndex], currentRow[columnIndex + 1] ); } } // Shift the current row into the next dependency. nextRow.swap(currentRow); } // The first retained value covers both strings. return nextRow[0]; }};// Driver codeint main() { string firstText = "abcde"; string secondText = "ace"; Solution obj; cout << obj.longestCommonSubsequence( firstText, secondText ) << endl; return 0;}Complexity Analysis
Time Complexity: O(M × N), where M and N are the lengths of the two strings, because every pair of character positions is processed once regardless of which string is chosen as the shorter one.
Space Complexity: O(min(M, N)), because only two rows are stored, with a width based on the shorter string, while all older rows are discarded.
Interview follow-up Questions
Yes. A subsequence preserves relative order but allows gaps between selected characters.
Be the first to add a comment.