The Longest Common Subsequence Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. The Longest Common Subsequence
  5. Discussions

The Longest Common Subsequence

Sort by

recency

|

154 Discussions

|

  • ysaakpr
     + 0 comments

    Please check your test case. This is giving a success output, but one of your test failing. Testcase 3 expecting : 27 76 88 55 94 42 56 74 69 7 94 41 8 71 15 43 3 23 49 84 98 89 24 20 14 88

    But 27 76 88 55 94 42 56 74 69 7 94 41 8 71 15 43 3 23 49 84 73 89 24 20 14 88 is also a valid sub secuence for input 50 46 16 27 89 79 60 76 24 88 55 94 57 42 56 74 24 95 55 33 69 29 14 7 94 41 8 71 12 15 43 3 23 49 84 78 73 63 5 46 98 26 40 76 41 89 24 20 68 14 88 26 27 76 88 0 55 99 94 70 34 42 31 47 56 74 69 46 93 88 89 7 94 41 68 37 8 71 57 15 43 89 43 3 23 35 49 38 84 98 47 89 73 24 20 14 88 75 

    package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

/*
 * Complete the 'longestCommonSubsequence' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts following parameters:
 *  1. INTEGER_ARRAY a
 *  2. INTEGER_ARRAY b
 */
// var store map[string][]int32
// func longestCommonSubsequence(a []int32, b []int32) []int32 {
//     store = make(map[string][]int32,10)
//     save(0,0,[]int32{})
//     return recursion(a,b)
// }

// func save(i,j int, val []int32) {
//     store[fmt.Sprintf("%d,%d", i,j)] = val
// }

// func get(i,j int) ([]int32,bool) {
//     v,ok := store[fmt.Sprintf("%d,%d", i,j)]
//     return v,ok
// }

var store [][][]int32
func initStore (a []int32, b []int32) {
    store = make([][][]int32,len(a)+1,len(a)+1)
    for i:= range store {
        store[i] = make([][]int32,len(b)+1,len(b)+1)
    }
}

func save(i,j int, val []int32) {
    store[i][j] = val
}

func get(i,j int) ([]int32,bool) {
    if store[i][j] == nil {
        return store[i][j],false
    } else {
        return store[i][j], true
    }
}

func largeArray(a,b []int32) []int32 {
    if len(a) > len(b) {
        return a
    }
    return b
}

func longestCommonSubsequence(a []int32, b []int32) []int32 {
    initStore(a,b)
    return recursion(a,b)
}

func recursion(a []int32, b []int32) []int32 {
    m,n := len(a),len(b)
 
    if (m == 0 || n==0) {
        return []int32{}
    }
    if v,ok:=get(m,n); ok {
        return v
    }
    a1 := a[0:m-1]
    b1 := b[0:n-1]
    
    if a[m-1] == b[n-1] {
        v:= append(recursion(a1,b1), a[m-1])
        save(m,n,v)
        return v
    } else {
        v := largeArray(recursion(a,b1),recursion(a1,b))
        save(m,n, v)
        return v
    }
}

func main() {
    reader := bufio.NewReaderSize(os.Stdin, 16 * 1024 * 1024)

    stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
    checkError(err)

    defer stdout.Close()

    writer := bufio.NewWriterSize(stdout, 16 * 1024 * 1024)

    firstMultipleInput := strings.Split(strings.TrimSpace(readLine(reader)), " ")

    nTemp, err := strconv.ParseInt(firstMultipleInput[0], 10, 64)
    checkError(err)
    n := int32(nTemp)

    mTemp, err := strconv.ParseInt(firstMultipleInput[1], 10, 64)
    checkError(err)
    m := int32(mTemp)

    aTemp := strings.Split(strings.TrimSpace(readLine(reader)), " ")

    var a []int32

    for i := 0; i < int(n); i++ {
        aItemTemp, err := strconv.ParseInt(aTemp[i], 10, 64)
        checkError(err)
        aItem := int32(aItemTemp)
        a = append(a, aItem)
    }

    bTemp := strings.Split(strings.TrimSpace(readLine(reader)), " ")

    var b []int32

    for i := 0; i < int(m); i++ {
        bItemTemp, err := strconv.ParseInt(bTemp[i], 10, 64)
        checkError(err)
        bItem := int32(bItemTemp)
        b = append(b, bItem)
    }

    result := longestCommonSubsequence(a, b)

    for i, resultItem := range result {
        fmt.Fprintf(writer, "%d", resultItem)

        if i != len(result) - 1 {
            fmt.Fprintf(writer, " ")
        }
    }

    fmt.Fprintf(writer, "\n")

    writer.Flush()
}

func readLine(reader *bufio.Reader) string {
    str, _, err := reader.ReadLine()
    if err == io.EOF {
        return ""
    }

    return strings.TrimRight(string(str), "\r\n")
}

func checkError(err error) {
    if err != nil {
        panic(err)
    }
}

  • 22it157
     + 0 comments

    include

    include

    include

    using namespace std;

    vector longestCommonSubsequence(vector& A, vector& B) { int m = A.size(); int n = B.size();

    // Initialize the DP table
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

// Fill the DP table
for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= n; ++j) {
        if (A[i - 1] == B[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
        } else {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
}

// Reconstruct the longest common subsequence
vector<int> lcs;
int i = m, j = n;
while (i > 0 && j > 0) {
    if (A[i - 1] == B[j - 1]) {
        lcs.push_back(A[i - 1]);
        i--;
        j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
        i--;
    } else {
        j--;
    }
}

reverse(lcs.begin(), lcs.end());
return lcs;

    }

    int main() { int m, n; cin >> m >> n;

    vector<int> A(m);
vector<int> B(n);

for (int i = 0; i < m; ++i) {
    cin >> A[i];
}

for (int i = 0; i < n; ++i) {
    cin >> B[i];
}

vector<int> result = longestCommonSubsequence(A, B);

// Print the longest common subsequence
for (int i = 0; i < result.size(); ++i) {
    cout << result[i] << " ";
}
cout << endl;

return 0;

    }

  • dehaka
     + 0 comments

    standard method on the internet

    vector<int> longest(const vector<int>& A, const vector<int>& B) {
    vector<vector<vector<int>>> M(A.size()+1, vector<vector<int>>(B.size()+1, {0, -1, -1}));
    for (int i=1; i < A.size()+1; i++) {
        for (int j=1; j < B.size()+1; j++) {
            if (A[i-1] == B[j-1]) M[i][j] = {M[i-1][j-1][0]+1, i-1, j-1};
            else if (M[i][j-1][0] > M[i-1][j][0]) M[i][j] = {M[i][j-1][0], i, j-1};
            else M[i][j] = {M[i-1][j][0], i-1, j};
        }
    }
    vector<int> result;
    int temp;
    int i = A.size(), j = B.size();
    while(i != 0 and j != 0) {
        if (A[i-1] == B[j-1]) result.push_back(A[i-1]);
        temp = M[i][j][2];
        i = M[i][j][1];
        j = temp;
    }
    return result;
}

int main()
{
    int n, m, k;
    vector<int> A, B;
    cin >> n >> m;
    for (int i=1; i <= n; i++) {
        cin >> k;
        A.push_back(k);
    }
    for (int i=1; i <= m; i++) {
        cin >> k;
        B.push_back(k);
    }
    vector<int> result = longest(A, B);
    for (int i = result.size()-1; i >= 0; i--) cout << result[i] << ' ';
}

  • thinhproee
     + 0 comments
    //package solve_problems;
/*
 * 2024 ^_^
 *ThinhNguyen97
 * 
 */

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;



public class Solve_problems 
{       
    static void solve(int[] X, int[] Y) {
        int n = X.length, m = Y.length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++)
            dp[i][0] = 0;

        for (int i = 0; i <= m; i++)
            dp[0][i] = 0;

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) 
            {
                if (X[i - 1] == Y[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }

        // Reconstruct the LCS
        int lcsLength = dp[n][m];
        int[] lcs = new int[lcsLength]; // Array to hold the LCS
        int index = lcsLength - 1;
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (X[i - 1] == Y[j - 1]) {
                // Current elements match, so they are part of the LCS
                lcs[index] = X[i - 1];
                i--;
                j--;
                index--;
            } else {
                // Move to the cell that gives maximum length of LCS
                if (dp[i - 1][j] > dp[i][j - 1])
                    i--;
                else
                    j--;
            }
        }

        // Print the LCS
        //System.out.println("Length of Longest Common Subsequence: " + lcsLength);
        //System.out.print("Longest Common Subsequence: ");
        for (int k = 0; k < lcsLength; k++)
            System.out.print(lcs[k] + " ");
        
        //System.out.println();
    }


    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
        ////////
        int n=sc.nextInt(), m=sc.nextInt();
        int[] X=new int[n];
        for(int i=0;i<n;i++)
            X[i]=sc.nextInt();
        
        int[] Y=new int[m];
        for(int i=0;i<m;i++)
            Y[i]=sc.nextInt();
        solve(X, Y);
            
        
        
        // Close the Scanner instance
        sc.close();
    }
}

  • yashparihar729
     + 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank The Longest Common Subsequence