HackerRank The Longest Common Subsequence

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.

HackerRank The Longest Common Subsequence Problem Solution

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])))

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python