In this post, we will solve HackerRank The Longest Common Subsequence Problem Solution. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. Longest common subsequence (LCS) of 2 sequences is a subsequence, with maximal length, which is common to both the sequences.
Given two sequences of integers, A = [a[1], a[2],…, a[n]] and B = b[1], b[2],, b[m]]. find the longest common subsequence and print it as a line of space-separated integers. If there are multiple common subsequences with the same maximum length, print any one of them.
In case multiple solutions exist, print any of them. It is guaranteed that at least one non-
empty common subsequence will exist.
Function Description
Complete the longestCommonSubsequence function in the editor below. It should return an integer array of a longest common subsequence.
longestCommonSubsequence has the following parameter(s):
- a: an array of integers
- b: an array of integers
Output Format
Print the longest common subsequence as a series of space-separated integers on one line. In case of multiple valid answers, print any one of them.
Sample Input
5 6
1 2 3 4 1
3 4 1 2 1 3
Sample Output
1 2 3
Explanation
There is no common subsequence with length larger than 3. And “1 2 3”, “1 2 1”, “3 4 1” are all correct answers.
The Longest Common Subsequence C Solution
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
int main(void)
{
int i,j;
int *s1;
int *s2;
int *s3;
int k,l;
scanf("%d",&(i));
scanf("%d",&(j));
int memory[i+1][j+1];
for(k=0;k<i+1;k++)
{
memory[k][0]=0;
}
for(k=0;k<j+1;k++)
{
memory[0][k]=0;
}
s1 = malloc(i*(sizeof(int)));
s2 = malloc(j*(sizeof(int)));
for(k=0;k<i;k++)
{
scanf("%d",&(s1[k]));
}
for(k=0;k<j;k++)
{
scanf("%d",&(s2[k]));
}
for(k=1;k<i+1;k++)
{
for(l=1;l<j+1;l++)
{
if(s1[k-1]==s2[l-1])
{
memory[k][l]=memory[k-1][l-1]+1;
}
else
{
memory[k][l]=memory[k-1][l];
if(memory[k-1][l] < memory[k][l-1])
{
memory[k][l]=memory[k][l-1];
}
}
}
}
//printf("%d",memory[i][j]);
s3 = malloc(memory[i][j]*(sizeof(int)));
k=i;
l=j;
int count=-1;
while(l!=0 && k!=0)
if(memory[k][l] == memory[k-1][l])
{
k=k-1;
}
else if(memory[k][l] == memory[k][l-1])
{
l=l-1;
}
else
{
k=k-1;
l=l-1;
count= count+1;
s3[count] = s2[l];
}
for(k=count;k>=0;k--)
{printf("%d ",s3[k]);
}
}
The Longest Common Subsequence C++ Solution
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,m,i,j;
cin>>n>>m;
int a[n+1],b[m+1],mat[n+1][m+1];
a[0]=b[0]=0;
for(i=0;++i<=n;cin>>a[i]);
for(i=0;++i<=m;cin>>b[i]);
for(i=-1;++i<=m;mat[0][i]=0);
for(i=-1;++i<=n;mat[i][0]=0);
for(i=0;++i<=n;)
{
for(j=0;++j<=m;)
{
if(a[i]==b[j])
mat[i][j]=mat[i-1][j-1]+1;
else
mat[i][j]=max(mat[i-1][j],mat[i][j-1]);
}
}
i=n;j=m;
int ans[mat[n][m]],p=mat[i][j],k=0;
while(mat[i][j]!=0)
{
if(p==mat[i][j-1])
{
j-=1;
p=mat[i][j];
}
else if(p==mat[i-1][j])
{
i-=1;
p=mat[i][j];
}
else if(p==(mat[i-1][j-1]+1))
{
ans[k]=a[i];
k+=1;
i-=1;
j-=1;
p=mat[i][j];
}
}
ans[k]=a[i];
for(i=mat[n][m];--i>=1;)
cout<<ans[i]<<" ";
cout<<ans[0];
return 0;
}The Longest Common Subsequence C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
static void Main(string[] args)
{
int[] arr = Console.ReadLine().Split(new char[] { '\r', '\n', '\t', ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(s => int.Parse(s)).ToArray();
int N = arr[0];
int M = arr[1];
int[] fstArr = Console.ReadLine().Split(new char[] { '\r', '\n', '\t', ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(s => int.Parse(s)).ToArray();
int[] sndArr = Console.ReadLine().Split(new char[] { '\r', '\n', '\t', ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(s => int.Parse(s)).ToArray();
int[,] res = new int[N + 1, M + 1];
int max = 0;
string finalAns = String.Empty;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
if (fstArr[i - 1] == sndArr[j - 1])
res[i, j] = res[i - 1, j - 1] + 1;
else
res[i, j] = Math.Max(res[i - 1, j], res[i, j - 1]);
}
}
max = res[N, M];
int x = N;
int y = M;
int[] lcs = new int[max];
while (x > 0 && y > 0)
{
if (fstArr[x - 1] == sndArr[y - 1])
{
lcs[max - 1] = fstArr[x - 1];
x--; y--; max--;
}
else if (res[x - 1, y] > res[x, y - 1])
x--;
else
y--;
}
Console.WriteLine(String.Join(" ", lcs));
}
}The Longest Common Subsequence Java Solution
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = scanner.nextInt();
}
int[] b = new int[m];
for (int i = 0; i < m; ++i) {
b[i] = scanner.nextInt();
}
int[][] opt = new int[n + 1][m + 1];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i - 1] == b[j - 1]) {
opt[i][j] = opt[i - 1][j - 1] + 1;
} else {
opt[i][j] = Math.max(opt[i][j - 1], opt[i - 1][j]);
}
}
}
//System.out.println(opt[n][m]);
int i = n, j = m;
Stack<Integer> stack = new Stack<>();
while (i > 0 && j > 0) {
if (a[i - 1] == b[j - 1]) {
stack.push(a[i - 1]);
i -= 1;
j -= 1;
} else if (opt[i][j - 1] >= opt[i - 1][j]) {
j -= 1;
} else if (opt[i][j - 1] < opt[i - 1][j]) {
i -= 1;
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop() + " ");
}
System.out.println(sb.toString().trim());
}
}The Longest Common Subsequence JavaScript Solution
function processData(input) {
const inputSplit = input.split('\n');
const seqOne = [null].concat(inputSplit[1].split(' ').map(Number));
const seqTwo = [null].concat(inputSplit[2].split(' ').map(Number));
const seqChecker = Array(seqOne.length)
.fill(0)
.map(() => Array(seqTwo.length).fill(0));
for(let row = 1; row < seqOne.length; row++) {
for(let col = 1; col < seqTwo.length; col++) {
if(seqOne[row] === seqTwo[col]) {
seqChecker[row][col] = seqChecker[row - 1][col - 1] + 1;
} else {
seqChecker[row][col] = Math.max(seqChecker[row - 1][col],
seqChecker[row][col - 1])
}
}
}
let row = seqOne.length - 1;
let col = seqTwo.length - 1;
const seqBuilder = [];
while(row > 0 && col > 0) {
if(seqChecker[row][col] - 1 === seqChecker[row - 1][col - 1]
&& seqChecker[row - 1][col] === seqChecker[row][col - 1]) {
seqBuilder.push(seqOne[row]);
row--;
col--;
} else if(seqChecker[row][col] == seqChecker[row - 1][col]) {
row--;
} else {
col--
}
}
console.log(seqBuilder.reverse().join(' '))
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});The Longest Common Subsequence Python Solution
n,m = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
s_lengths = [[0 for _ in range(m+1)] for _ in range(n+1)]
sequences = [[[] for _ in range(m+1)] for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,m+1):
if A[i-1] == B[j-1]:
s_lengths[i][j] = 1 + s_lengths[i-1][j-1]
sequences[i][j] = list(sequences[i-1][j-1])
sequences[i][j].append(A[i-1])
else:
if s_lengths[i-1][j] >= s_lengths[i][j-1]:
s_lengths[i][j] = s_lengths[i-1][j]
sequences[i][j] = sequences[i-1][j]
else:
s_lengths[i][j] = s_lengths[i][j-1]
sequences[i][j] = sequences[i][j-1]
print(" ".join(map(str,sequences[-1][-1])))
