← Back to DSA Course | Chapter 14: Dynamic Programming | Lesson 6 of 12

Longest Common Subsequence क्या है

Longest common subsequence दो words में उसी order में दिखने वाले letters का सबसे लंबा set ढूंढने जैसा है, भले ही उनके बीच दूसरे letters हों।

In this page:

  1. LCS Idea
  2. DP State
  3. Transition
  4. Reconstruct LCS
  5. Practice
Syntax
markup 
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
    for j in range(1, n + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

LCS Idea

दो strings का longest common subsequence characters का सबसे लंबा sequence है जो दोनों में, उसी relative order में दिखता है, लेकिन ज़रूरी नहीं touching हो — ace abcde का एक subsequence है भले ही letters adjacent न हों।

उदाहरण: LCS Idea

#include <iostream>
using namespace std;
int main() {
	string a = "abcde", b = "ace";
	cout << "'" << b << "' is a subsequence of '" << a << "' (same order, not necessarily touching)";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		String a = "abcde", b = "ace";
		System.out.println("'" + b + "' is a subsequence of '" + a + "' (same order, not necessarily touching)");
	}
}
a, b = "abcde", "ace"
print(f"'{b}' is a subsequence of '{a}' (same order, not necessarily touching)")
#include <stdio.h>
int main() {
	char a[] = "abcde", b[] = "ace";
	printf("'%s' is a subsequence of '%s' (same order, not necessarily touching)", b, a);
	return 0;
}

DP State

dp[i][j] पहली string के सिर्फ पहले i characters और दूसरी string के पहले j characters उपयोग करते हुए LCS length store करता है, इसलिए यह table prefix by prefix भरना पूरी strings के answer तक बनता है।

उदाहरण: DP State

#include <iostream>
using namespace std;
int main() {
	int dp[6][4] = {0};
	cout << "dp[i][j] = LCS length using first i chars of string1, first j chars of string2";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[][] dp = new int[6][4];
		System.out.println("dp[i][j] = LCS length using first i chars of string1, first j chars of string2");
	}
}
dp = [[0]*4 for _ in range(6)]
print("dp[i][j] = LCS length using first i chars of string1, first j chars of string2")
#include <stdio.h>
int main() {
	int dp[6][4] = {0};
	printf("dp[i][j] = LCS length using first i chars of string1, first j chars of string2");
	return 0;
}

Transition

अगर दोनों strings के current characters match करें, LCS diagonal value से (dp[i-1][j-1] + 1) एक से बढ़ता है; अगर वे match न करें, आप सबसे अच्छा जो कर सकते हैं वह है किसी एक string से एक character ignore करने में बेहतर (dp[i-1][j] और dp[i][j-1] का max)।

उदाहरण: Transition

#include <iostream>
using namespace std;
int main() {
	string a = "abcde", b = "ace";
	int n = a.size(), m = b.size();
	int dp[6][4] = {0};
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] = a[i-1]==b[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);
	cout << "LCS length: " << dp[n][m];
	return 0;
}
public class Main {
	public static void main(String[] args) {
		String a = "abcde", b = "ace";
		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) ? dp[i-1][j-1]+1 : Math.max(dp[i-1][j], dp[i][j-1]);
		System.out.println("LCS length: " + dp[n][m]);
	}
}
a, b = "abcde", "ace"
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("LCS length:", dp[n][m])
#include <stdio.h>
#include <string.h>
int main() {
	char a[] = "abcde", b[] = "ace";
	int n = strlen(a), m = strlen(b);
	int dp[6][4] = {0};
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (a[i-1]==b[j-1]) dp[i][j] = dp[i-1][j-1]+1;
			else dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
		}
	printf("LCS length: %d", dp[n][m]);
	return 0;
}

Reconstruct LCS

सिर्फ length से आगे, bottom-right corner से भरी हुई table के through वापस trace करना — matches पर diagonal moves और mismatches पर बड़ा neighbor follow करते हुए — असली subsequence reconstruct करता है, सिर्फ इसकी length नहीं।

उदाहरण: Reconstruct LCS

#include <iostream>
using namespace std;
int main() {
	string a = "abcde", b = "ace";
	int n = a.size(), m = b.size();
	int dp[6][4] = {0};
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] = a[i-1]==b[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);
	string result; int i = n, j = m;
	while (i > 0 && j > 0) {
		if (a[i-1] == b[j-1]) { result = a[i-1] + result; i--; j--; }
		else if (dp[i-1][j] > dp[i][j-1]) i--;
		else j--;
	}
	cout << "Reconstructed LCS: " << result;
	return 0;
}
public class Main {
	public static void main(String[] args) {
		String a = "abcde", b = "ace";
		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) ? dp[i-1][j-1]+1 : Math.max(dp[i-1][j], dp[i][j-1]);
		StringBuilder result = new StringBuilder();
		int i = n, j = m;
		while (i > 0 && j > 0) {
			if (a.charAt(i-1) == b.charAt(j-1)) { result.insert(0, a.charAt(i-1)); i--; j--; }
			else if (dp[i-1][j] > dp[i][j-1]) i--;
			else j--;
		}
		System.out.println("Reconstructed LCS: " + result);
	}
}
a, b = "abcde", "ace"
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])
result = []
i, j = n, m
while i > 0 and j > 0:
    if a[i-1] == b[j-1]:
        result.append(a[i-1]); i -= 1; j -= 1
    elif dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1
print("Reconstructed LCS:", "".join(reversed(result)))
#include <stdio.h>
#include <string.h>
int main() {
	char a[] = "abcde", b[] = "ace", result[10];
	int n = strlen(a), m = strlen(b), dp[6][4] = {0};
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (a[i-1]==b[j-1]) dp[i][j] = dp[i-1][j-1]+1;
			else dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
		}
	int i = n, j = m, k = 0;
	while (i > 0 && j > 0) {
		if (a[i-1] == b[j-1]) { result[k++] = a[i-1]; i--; j--; }
		else if (dp[i-1][j] > dp[i][j-1]) i--;
		else j--;
	}
	result[k] = '\0';
	for (int x = 0; x < k/2; x++) { char t = result[x]; result[x] = result[k-1-x]; result[k-1-x] = t; }
	printf("Reconstructed LCS: %s", result);
	return 0;
}

Practice

LCS सीधे diff tools में दिखता है जो किसी file के दो versions के बीच क्या बदला highlight करते हैं, और DNA sequence comparison में जहां researchers दो sequences के बीच shared genetic patterns ढूंढते हैं।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "LCS powers diff tools (what changed between file versions) and DNA sequence comparison";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("LCS powers diff tools (what changed between file versions) and DNA sequence comparison");
	}
}
print("LCS powers diff tools (what changed between file versions) and DNA sequence comparison")
#include <stdio.h>
int main() {
	printf("LCS powers diff tools (what changed between file versions) and DNA sequence comparison");
	return 0;
}
Related Topics

Longest Increasing Subsequence क्या है · सामान्य Bit Tricks · Lowest Common Ancestor ढूँढना · Unbounded Knapsack समस्या

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. Subsequence (contiguous नहीं) को substring (contiguous) के साथ confuse करना।
  2. एक match पर dp[i - 1][j - 1] + 1 के बजाय max उपयोग करना, या + 1 भूल जाना।
  3. Table को n x m के रूप में size देना बजाय (n + 1) x (m + 1) के ताकि index 0 एक empty prefix represent न कर सके।
🔒

Chapter Quiz — Complete all 12 topics to unlock

0/12 topics done

Complete these topics first:

← Previous Lesson Unbounded Knapsack Next Lesson → Longest Increasing Subsequence

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.