Longest Common Subsequence - Practice Coding Problems

Longest Common Subsequence - Problem

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Input & Output

Example 1 — Basic Case

$ Input: text1 = "abcde", text2 = "ace"

› Output: 3

💡 Note: The longest common subsequence is "ace" with length 3. Characters 'a', 'c', 'e' appear in both strings in the same order.

Example 2 — Partial Match

$ Input: text1 = "abc", text2 = "abc"

› Output: 3

💡 Note: Both strings are identical, so the LCS is the entire string "abc" with length 3.

Example 3 — No Common Subsequence

$ Input: text1 = "abc", text2 = "def"

› Output: 0

💡 Note: No characters are common between the two strings, so LCS length is 0.

Constraints

1 ≤ text1.length, text2.length ≤ 1000
text1 and text2 consist of only lowercase English characters.

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings text1="abcde" and text2="ace"

Process

Find longest subsequence preserving character order

Output

Length of LCS = 3 (subsequence "ace")

Key Takeaway

🎯 Key Insight: Use dynamic programming to build the solution by comparing characters and taking optimal choices at each step

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to use dynamic programming to build up the solution. When characters match, we extend the previous best subsequence by 1. When they don't match, we take the maximum from either skipping a character from the first or second string. The optimal 2D DP approach fills a table bottom-up. Time: O(n×m), Space: O(n×m).

Common Approaches

Approach	Time	Space	Notes
✓ 2D Dynamic Programming - Bottom-Up Approach	O(n × m)	O(n × m)	Build a 2D table where dp[i][j] represents LCS length of first i and first j characters
Brute Force - Try All Subsequences	O(2^n × m)	O(n)	Generate all subsequences of first string and check if they exist in second string
Memoization - Top-Down Dynamic Programming	O(n × m)	O(n × m)	Use recursion with memoization to avoid recalculating the same subproblems

2D Dynamic Programming - Bottom-Up Approach — Algorithm Steps

Create (n+1) × (m+1) DP table
Initialize base cases (empty strings)
Fill table: if chars match, dp[i][j] = dp[i-1][j-1] + 1
Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Table

Create (n+1)×(m+1) table with zeros

Fill Cells

Use recurrence relation to fill each cell

Get Result

Bottom-right cell contains the answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(char* text1, char* text2) {
    int n = strlen(text1), m = strlen(text2);
    int** dp = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int*)calloc(m + 1, sizeof(int));
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    int result = dp[n][m];
    
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int main() {
    char text1[1001], text2[1001];
    fgets(text1, sizeof(text1), stdin);
    fgets(text2, sizeof(text2), stdin);
    text1[strcspn(text1, "\n")] = 0;
    text2[strcspn(text2, "\n")] = 0;
    printf("%d\n", solution(text1, text2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

Fill n×m table with constant work per cell

✓ Linear Growth

Space Complexity

O(n × m)

2D DP table of size (n+1)×(m+1)

⚡ Linearithmic Space

125.0K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

2D Dynamic Programming - Bottom-Up Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler