Longest Common Subsequence in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

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

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

int main() {
    char a[100], b[100];
    scanf("%s%s", a, b);
    int n = strlen(a), m = strlen(b), dp[101][101] = {};
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            dp[i][j] = (a[i-1]==b[j-1]) ? 1+dp[i-1][j-1] : max(dp[i-1][j], dp[i][j-1]);
    printf("%d", dp[n][m]);
}

C Output

Input:  
abcde  
ace  

Output:  
3

C++ Program

#include<iostream>
#include<string>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size(), dp[101][101] = {};
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            dp[i][j] = (a[i-1]==b[j-1]) ? 1+dp[i-1][j-1] : max(dp[i-1][j], dp[i][j-1]);
    cout << dp[n][m];
}

C++ Output

Input:  
abc  
abc  

Output:  
3

JAVA Program

import java.util.*;

class LCS {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next(), b = sc.next();
        int n = a.length(), m = b.length();
        int[][] dp = new int[n+1][m+1];
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                dp[i][j] = (a.charAt(i-1)==b.charAt(j-1)) ? 1+dp[i-1][j-1] : Math.max(dp[i-1][j], dp[i][j-1]);
        System.out.print(dp[n][m]);
    }
}

JAVA Output

Input:  
aggtab  
gxtxayb  

Output:  
4

Python Program

a, b = input(), input()
n, m = len(a), len(b)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = dp[i-1][j-1]+1 if a[i-1]==b[j-1] else max(dp[i-1][j], dp[i][j-1])
print(dp[n][m])

Python Output

Input:  
abcdef  
acf  

Output:  
3

In-Depth Learning – Entire Concept in Paragraphs

What Is the Longest Common Subsequence (LCS)?

A subsequence is a string that can be obtained from another string by removing zero or more characters but keeping the position of the remaining characters the same. The Longest Common Subsequence of two strings is the longest common subsequence that both strings have, not necessarily in consecutive positions.

For instance, "ace" is a subsequence of "abcde" and "acf" is a subsequence of "abcdef". The important point is: the characters need to come in sequence, but not necessarily consecutively.

How the Code Works

We apply Dynamic Programming (DP) in solving this problem efficiently. The main concept is to construct a 2D array dp[i][j] such that:

i is the length of the prefix of the first string.

j is the prefix length of the second string.

dp[i][j] contains the length of LCS of a[0…i-1] and b[0…j-1].

The recursive formula is:

If a[i-1] == b[j-1]: add this character → dp[i][j] = 1 + dp[i-1][j-1]

Else: skip one character from one of the strings → dp[i][j] = max(dp[i-1][j], dp[i][j-1])

We set the first row and column to 0 as LCS with an empty string is always 0.

The answer is at dp[n][m] — when n and m are the two string lengths.

Example

Input:

a = "abcde", b = "ace"

Explanation:

Common subsequence characters: "a", "c", "e"

So, LCS length = 3

Real-Life Analogy

Suppose two friends describe to you what they recall from a film. The descriptions of each are different, but they share some common scenes — those are your common subsequences. The longest of these matching sequences is the LCS of their recollections.

In DNA sequencing, LCS is utilized to determine similar gene structures among species or individuals. In file comparison software, it identifies unchanged lines across versions.

Where and When Is It Used?

LCS algorithm is used extensively in:

Version control systems such as Git (diff tools)

DNA and genome sequencing

Plagiarism detectors

Text comparison utilities

Spell check and autocorrect algorithms

Dynamic programming interviews

This is a top 10 dynamic programming problem frequently asked during interviews by Google, Amazon, Microsoft, etc.

Time and Space Complexity

Operation\tComplexity

Time\tO(n × m)

Space\tO(n × m)

You can do it in O(min(n, m)) space using rolling arrays, but that introduces complexity and isn't necessary for basic learning.

Python-Specific Tip

If you want to print the actual LCS, you can backtrack dp[][] array from dp[n][m]:

python

res = []

i, j = n, m

while i and j:

    if a[i-1] == b[j-1]:

        res.append(a[i-1])

i -= 1; j -= 1

elif dp[i-1][j] > dp[i][j-1]: i -= 1

else: j -= 1

print(''.join(reversed(res)))

SEO-Optimized Natural Paragraph for Ranking

Want to get the Longest Common Subsequence (LCS) between two strings in C, C++, Java, or Python? This tutorial provides a concise and effective dynamic programming solution to find LCS length via a 2D matrix. LCS is essential in text comparison, diff tools, genome sequencing, and coding interviews. This tutorial breaks down the recursive logic, dynamic array filling, and real-world applications in an easy-to-understand and detailed manner. It takes mastery of this problem to have a solid base in dynamic programming, string manipulation, and algorithmic thinking.