HackerRank The Longest Common Subsequence problem solution

In this 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.

You have given two sequences of integers, A = [a[1], … , a[n]] and B = [b[1],….,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.

HackerRank The Longest Common Subsequence problem solution in Python.

#!/bin/python3

import sys   

# parse input
n,m = input().strip().split(' ')
n = int(n)
m = int(m)
A = [int(x) for x in input().strip().split(' ')]
B = [int(x) for x in input().strip().split(' ')]

# initialize table for DP
table = dict()
for i in range(0,n+1):
    loc = tuple([i,0])
    table[loc] = list()

for j in range(0,m+1):
    loc = tuple([0,j])
    table[loc] = list()

# populate table
for i in range(1,n+1):
    for j in range(1,m+1):
        a = A[i-1]
        b = B[j-1]
        if a == b:
            seq = table[tuple([i-1,j-1])].copy()
            seq.append(a)
            table[tuple([i,j])] = seq
        else:
            ti = table[tuple([i-1,j])].copy()
            tj = table[tuple([i,j-1])].copy()
            
            if len(ti) > len(tj):
                table[tuple([i,j])] = ti.copy()
            else:
                table[tuple([i,j])] = tj.copy()
 
# output result
out = table[tuple([n,m])]
out = ' '.join(str(x) for x in out)
print(out)

The Longest Common Subsequence problem solution in Java.

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());
    }
}

Problem solution in C++.

#include <ios>
#include <iostream>

int dp[105][105] = {};
int parenti[105][105] = {};
int parentj[105][105] = {};
int arr1[105] = {};
int arr2[105] = {};
int n, m;
bool first = true;

int lcs(int i, int j)
{
    if (i == -1) return 0;
    else if (j == -1) return 0;
    else if (dp[i][j] == -1)
    {
        if (arr1[i] == arr2[j])
        {
            dp[i][j] = lcs(i-1, j-1)+1;
            parenti[i][j] = i-1;
            parentj[i][j] = j-1;
        }
        else
        {
            if (lcs(i-1, j) > lcs(i, j-1))
            {
                dp[i][j] = lcs(i-1, j);
                parenti[i][j] = i-1;
                parentj[i][j] = j;
            }
            else
            {
                dp[i][j] = lcs(i, j-1);
                parenti[i][j] = i;
                parentj[i][j] = j-1;
            }
        }
    }
    return dp[i][j];
}

void print(int i, int j)
{
    if (i != -1 && j != -1)
    {
        print(parenti[i][j], parentj[i][j]);
        if (arr1[i] == arr2[j])
        {
            if (first) first = false;
            else std::cout << " ";
            std::cout << arr1[i];
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    for (int i = 0; i < 105; i++)
    {
        for (int j = 0; j < 105; j++)
        {
            dp[i][j] = -1;
            parenti[i][j] = -1;
            parentj[i][j] = -1;
        }
    }
    std::cin >> n >> m;
    for (int i = 0; i < n; i++) std::cin >> arr1[i];
    for (int i = 0; i < m; i++) std::cin >> arr2[i];
    lcs(n-1, m-1);
    print(n-1, m-1);
}

Problem solution in C.

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int* longestCommonSubsequence(int a_size, int* a, int b_size, int* b, int *result_size) {
    int memo[a_size + 1][b_size + 1];

    // initialize table.
    for (int i = 0; i <= a_size; i++)
        memo[i][0] = 0;

    for (int j = 1; j <= b_size; j++)
        memo[0][j] = 0;

    // Find the length of the longest substring
    for (int i = 1, r = 0; i <= a_size; i++, r++)
        for (int j = 1, c = 0; j <= b_size; j++, c++)
            if (a[r] == b[c])
                memo[i][j] = memo[i - 1][j - 1] + 1;
            else
                memo[i][j] = (memo[i - 1][j] > memo[i][j - 1]) ? memo[i - 1][j] : memo[i][j - 1];

    // Read the memo backwards to find the LCS
    int len = memo[a_size][b_size];
    int r = a_size;
    int c = b_size;
    int* result = (int*)malloc(sizeof(int) * len);
    while (len) {
        if (a[r-1] == b[c-1]) {
            --len;
            --r;
            --c;
            result[len] = a[r];
        }
        else if (memo[r - 1][c] == len)
            --r;
        else
            --c;
    }

    *result_size = memo[a_size][b_size];
    return result;
}

int main() {
    int n; 
    int m; 
    scanf("%i %i", &n, &m);
    int *a = malloc(sizeof(int) * n);
    for (int a_i = 0; a_i < n; a_i++) {
       scanf("%i",&a[a_i]);
    }
    int *b = malloc(sizeof(int) * m);
    for (int b_i = 0; b_i < m; b_i++) {
       scanf("%i",&b[b_i]);
    }
    int result_size;
    int* result = longestCommonSubsequence(n, a, m, b, &result_size);
    for(int result_i = 0; result_i < result_size; result_i++) {
        if(result_i) {
            printf(" ");
        }
        printf("%d", result[result_i]);
    }
    puts("");


    return 0;
}