Problem 3
Problem statement:
Implement Longest Common Subsequence using C programming.
Concept:
The Longest Common Subsequence (LCS) problem is solved using Dynamic Programming. The idea is
to break the problem into smaller overlapping subproblems and store their solutions in a table to
avoid repeated computations. For two strings, a two-dimensional table is created where each cell
represents the length of the LCS for prefixes of the strings. If the current characters of both strings
match, the value is increased by one from the previous diagonal cell. If they do not match, the
maximum value from the adjacent left or top cell is taken. This approach efficiently computes the LCS
length and also allows backtracking through the table to reconstruct the actual subsequence.
Pseudocode:
Algorithm LCS(S1, S2)
Input:
S1, S2 are two strings
Output:
Length of LCS and the LCS sequence
m ← length of S1
n ← length of S2
Create table dp[0…m][0…n]
for i ← 0 to m
dp[i][0] ← 0
for j ← 0 to n
dp[0][j] ← 0
for i ← 1 to m
for j ← 1 to n
if S1[i − 1] = S2[j − 1] then
dp[i][j] ← dp[i − 1][j − 1] + 1
else
dp[i][j] ← max(dp[i − 1][j], dp[i][j − 1])
Length ← dp[m][n]
Create array LCS of size Length
index ← Length − 1
i ← m, j ← n
while i > 0 and j > 0
if S1[i − 1] = S2[j − 1] then
LCS[index] ← S1[i − 1]
index ← index − 1
i←i−1
j←j−1
else if dp[i − 1][j] > dp[i][j − 1] then
i←i−1
else
j←j−1
Print Length
Print LCS
End Algorithm
Code:
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return (a > b) ? a : b;
int main() {
char S1[100], S2[100];
printf("Enter first string: ");
scanf("%s", S1);
printf("Enter second string: ");
scanf("%s", S2);
int m = strlen(S1);
int n = strlen(S2);
int dp[m+1][n+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (S1[i-1] == S2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
printf("\nLength of LCS = %d\n", dp[m][n]);
char lcs[dp[m][n] + 1];
lcs[dp[m][n]] = '\0';
int i = m, j = n, index = dp[m][n] - 1;
while (i > 0 && j > 0) {
if (S1[i-1] == S2[j-1]) {
lcs[index--] = S1[i-1];
i--;
j--;
else if (dp[i-1][j] > dp[i][j-1])
i--;
else
j--;
printf("Longest Common Subsequence: %s\n", lcs);
return 0;
Output:
Time complexity:
The time complexity of the Longest Common Subsequence (LCS) algorithm using dynamic
programming is O(m × n), where m and n are the lengths of the two input strings. This is because a
two-dimensional table of size (m+1) × (n+1) is filled, and each cell is computed exactly once using
constant-time operations. The backtracking step to construct the subsequence takes at most O(m +
n) time, which does not change the overall time complexity. Hence, the total time complexity
remains O(m × n).