# The Longest Common Subsequence

### Problem Statement :

```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,a,..,a[n]] and B = [b,b,...,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.

Recommended References

This Youtube video tutorial explains the problem and its solution quite well.

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
Input Format

The first line contains two space separated integers n and m, the sizes of sequences A and B.
The next line contains n space-separated integers A[i].
The next line contains m space-separated integers B[j].

Constraints
1 <= n <= 100
1 <= m<= 100
0 <= a[i] < 1000, where i ∈ [1,n]
0 <= b[j] <= 1000, where j ∈ [1,m]

Constraints
1 <= n,m <= 100
0 <= a[i],b[j] <1000

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.```

### Solution :

```                            ```Solution in C :

In C++ :

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void LCS(const vector<int> &A, const vector<int> &B) {
int n = A.size(), m = B.size();
vector<int> lens(m+1,0);
vector<vector<int>> prev(n+1,vector<int>(m+1,0));
int topleft;
for(int i = 1; i <= n; i++) {
topleft = 0;
for(int j = 1; j <= m; j++) {
int len;
if(A[i-1] == B[j-1]) {
len = topleft+1;
prev[i][j] = 1; // topleft
} else {
if(lens[j] > lens[j-1]) {
len = lens[j];
prev[i][j] = 2; // top
} else {
len = lens[j-1];
prev[i][j] = 3; // left
}
}
topleft = lens[j];
lens[j] = len;
}
}
// print LCS
int i = n, j = m, idx = 0;
vector<int> lcs(lens[m],0);
while(prev[i][j] != 0) {
if(prev[i][j] == 1) {
lcs[idx++] = A[i-1];
i--;
j--;
} else if(prev[i][j] == 2) {
i--;
} else {
j--;
}
}
for(int i = lcs.size()-1; i >= 0; i--) {
if(i != 0) {
cout << lcs[i] << ' ';
} else {
cout << lcs << endl;
}
}
}

int main() {
int n, m;
cin >> n >> m;
vector<int> A(n), B(m);
for(int i = 0 ; i < n; i++) {
cin >> A[i];
}
for(int i = 0; i < m; i++) {
cin >> B[i];
}
LCS(A,B);
return 0;
}

In Java :

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int sizeM = s.nextInt();
int sizeN = s.nextInt();
int[] m = new int[sizeM];
for (int i = 0; i < sizeM; i++) {
m[i] = s.nextInt();
}
int[] n = new int[sizeN];
for (int i = 0; i < sizeN; i++) {
n[i] = s.nextInt();
}
System.out.println(LCS(m, n));
}

private static String LCS(int[] m, int[] n) {
int[][] table = new int[m.length + 1][n.length + 1];
for (int i = 1; i < table.length; i++) {
for (int j = 1; j < table[i].length; j++) {
if (m[i - 1] == n[j - 1]) table[i][j] = table[i - 1][j - 1] + 1;
else table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
}
}
StringBuilder sb = new StringBuilder();
int i = m.length;
int j = n.length;
while (i > 0 && j > 0) {
int s = table[i][j];
int x = table[i - 1][j - 1];
int y = table[i - 1][j];
int z = table[i][j - 1];
if (s > x && s > y && s > z) {
sb.insert(0, " " + m[i - 1]); i--; j--;
}
else if (y > z) i--;
else j--;
}
return sb.deleteCharAt(0).toString();
}
}

In C :

#include <stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
int lcs;
int a,b;
int f;
void backtrack(i,j){
if(i==0||j==0);
else if(a[i]==b[j])backtrack(i-1,j-1),f=printf(f?" %d":"%d",a[i]);
else if(lcs[i][j-1]>lcs[i-1][j])backtrack(i,j-1);
else backtrack(i-1,j);
}
main(){
int i,j,_a,_b;
scanf("%d%d",&_a,&_b);
for(i=1;i<=_a;i++)scanf("%d",a+i);
for(i=1;i<=_b;i++)scanf("%d",b+i);
for(i=1;i<=_a;i++)
for(j=1;j<=_b;j++)
lcs[i][j]=max(max(lcs[i-1][j],lcs[i][j-1]),lcs[i-1][j-1]+(a[i]==b[j]));
backtrack(_a,_b);puts("");
}

In Python3 :

def backtrack(c, x, y, i=None, j=None):
i = i if i is not None else len(x) - 1
j = j if j is not None else len(y) - 1

if i < 0 or j < 0:
return []

if x[i] == y[j]:
return backtrack(c, x, y, i-1, j-1) + [x[i]]

if c[i][j-1] > c[i-1][j]:
return backtrack(c, x, y, i, j-1)

return backtrack(c, x, y, i-1, j)

def lcs(x, y):
c = [[0 for j in range(len(y) + 1)] for i in range(len(x) + 1)]
for i in range(len(x)):
for j in range(len(y)):
if x[i] == y[j]:
c[i][j] = c[i-1][j-1] + 1
else:
c[i][j] = max(c[i][j-1], c[i-1][j])
return backtrack(c, x, y)
return c[len(x)-1][len(y)-1]

if __name__ == '__main__':
n, m = map(int, input().split())
A, B = (list(map(int, input().split())) for i in range(2))
result = lcs(A, B)
print(' '.join(map(str, result)))```
```

## Inserting a Node Into a Sorted Doubly Linked List

Given a reference to the head of a doubly-linked list and an integer ,data , create a new DoublyLinkedListNode object having data value data and insert it at the proper location to maintain the sort. Example head refers to the list 1 <-> 2 <-> 4 - > NULL. data = 3 Return a reference to the new list: 1 <-> 2 <-> 4 - > NULL , Function Description Complete the sortedInsert function

## Reverse a doubly linked list

This challenge is part of a tutorial track by MyCodeSchool Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. Note: The head node might be NULL to indicate that the list is empty.

## Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

## Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

## Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your \$inOrder* func

## Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary