Find the Longest Common Subsequence (LCS) in given K permutations

0 0 8 minutes read

Given K permutations of numbers from 1 to N in a 2D array arr[][]. The task is to find the longest common subsequence of these K permutations.

Examples:

Input: N = 4, K = 3
arr[][] = {{1, 4, 2, 3},
{4, 1, 2, 3},
{1, 2, 4, 3}}
Output: 3
Explanation: Longest common subsequence is {1, 2, 3} which has length 3.

Input: N = 6, K = 3,
arr[][] = {{2, 5, 1, 4, 6, 3},
{5, 1, 4, 3, 2, 6},
{5, 4, 2, 6, 3, 1}}
Output: 3
Explanation: Longest common subsequence is {5, 4, 6} which has length 3.

Approach: This problem is an extension of longest common subsequence. The solution is based on the concept of dynamic programming. Follow the steps below:

Create a 2D array(pos[][]) to store position of all the numbers from 1 to N in each sequence, where pos[i][j] denotes position of value j in ith sequence.
Initialize an array(dp[]) where dp[i] stores the longest common subsequence ending at position i.
- Consider the first sequence as reference and for each element of the first sequence check the relative positions of them in other sequences.
  - Iterate over all possible indices j such that j < i and see if value at index i of the first sequence can be appended to the longest increasing subsequence ending at j.
  - This is done by checking if position of the number arr[0][j] is less than equal to position of the value arr[0][i] in all the permutations. Then the value at arr[0][i] can be appended to the sequence ending at position j.
So the recurrence is dp[i] = max(dp[i], 1 + dp[j]).
The maximum value from the array dp[] is the answer.

See the following illustration:

Illustration:

Take the following example:
N = 4, K = 3, arr[][] = {{1, 4, 2, 3},
{4, 1, 2, 3},
{1, 2, 4, 3}}

Form the position array: pos[][] = {{1, 3, 4, 2},
{2, 3, 4, 1},
{1, 2, 4, 3}}
In first sequence 1 is in 1st position, 2 in 3rd position, 3 in 4th and 4 in 2nd position. And so on for the other sequences.

Initialize dp[] array: The dp[] array is initialized and it initially dp[] = {0, 0, 0, 0}

Reference sequence: The first sequence i{1, 4, 2, 3} is used as the reference sequence i.e. relative positions of elements in other sequences are checked according to this one.

For i = 1: dp[1] = 1 because any sequence of length 1 is a increasing sequence. Now dp[] = {1, 0, 0, 0}

For i = 2: Now relative position of 4 and 1 will be checked in all the 3 sequences. In 2nd sequence and 3rd sequence the relative position is not maintained. So dp[2] = dp[1]. Now dp[] = {1, 1, 0, 0}.

For i = 3: Relative positions of (1, 4, 2) are checked.
When j = 1 i.e. value relative position of 1 and 2 are checked it satisfies the condition pos[ind][arr[1][1]] < pos[ind][arr[1][3]] for all ind in range [1, K]. So dp[3] = max(dp[3], dp[1]+1) = max(0, 2) = 2.
Now dp[] = {1, 1, 2, 0}

For i = 4: Here also when j = 3, then pos[ind][arr[1][3]] < pos[ind][arr[1][4]] for all ind in range [1, K]. So the 4th element of 1st sequence can be appended in the longest increasing subsequence ending at 3rd index. dp[4] = dp[3] + 1 = 2 + 1 = 3.
Now dp[] = {1, 1, 2, 3}

The maximum value in dp[] is 3. Therefore, the maximum length of the longest increasing subsequence is 3.

Note: 0 based indexing is used in the actual implementation. Here 1 based indexing is used for easy understanding

Below is the implementation of the above approach.

C++

// C++ code to find the longest common
// sub sequence of k permutations.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the longest common
// sub sequence of k permutations.
int findLcs(vector<vector<int>> &arr, 
            int n, int k)
{
    // Variable to keep track of the length
    // of the longest common sub sequence
    int maxLen = 0;
 
    // position array to keep track 
    // of position of elements 
    // in each permutation
    int pos[k][n];
 
    // Array to store the length of LCS
    int dp[n];
 
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < n; j++)
        {
            pos[i][arr[i][j] - 1] = j;
        }
    }
     
    // Loop to calculate the LCS 
    // of all the permutations
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
        for (int j = 0; j < i; j++)
        {
            bool good = true;
            for (int p = 0; p < k; p++)
            {
                if (pos[p][arr[0][j] - 1] 
                    > pos[p][arr[0][i] - 1])
                {
                    good = false;
                    break;
                }
            }
            if (good)
            {
                dp[i] = max(dp[i], 1 + dp[j]);
                maxLen = max(maxLen, dp[i]);
            }
        }
    }
    return maxLen;
}
 
// Driver code
int main()
{
    vector<vector<int>> arr = 
    {{2, 5, 1, 4, 6, 3},
     {5, 1, 4, 3, 2, 6},
     {5, 4, 2, 6, 3, 1}};
    int N = arr[0].size();
    int K = 3;
 
    // Function Call
    cout << findLcs(arr, N, K);
 
    return 0;
}

Java

// Java code to find the longest common
// sub sequence of k permutations.
import java.util.*;
 
class GFG{
 
// Function to find the longest common
// sub sequence of k permutations.
static int findLcs(int[][]arr, 
            int n, int k)
{
    // Variable to keep track of the length
    // of the longest common sub sequence
    int maxLen = 0;
 
    // position array to keep track 
    // of position of elements 
    // in each permutation
    int [][]pos = new int[k][n];
 
    // Array to store the length of LCS
    int []dp = new int[n];
 
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < n; j++)
        {
            pos[i][arr[i][j] - 1] = j;
        }
    }
     
    // Loop to calculate the LCS 
    // of all the permutations
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
        for (int j = 0; j < i; j++)
        {
            boolean good = true;
            for (int p = 0; p < k; p++)
            {
                if (pos[p][arr[0][j] - 1] 
                    > pos[p][arr[0][i] - 1])
                {
                    good = false;
                    break;
                }
            }
            if (good)
            {
                dp[i] = Math.max(dp[i], 1 + dp[j]);
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
    }
    return maxLen;
}
 
// Driver code
public static void main(String[] args)
{
    int[][] arr = 
    {{2, 5, 1, 4, 6, 3},
     {5, 1, 4, 3, 2, 6},
     {5, 4, 2, 6, 3, 1}};
    int N = arr[0].length;
    int K = 3;
 
    // Function Call
    System.out.print(findLcs(arr, N, K));
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python code for the above approach
 
# Function to find the longest common
# sub sequence of k permutations.
def findLcs(arr, n, k):
 
    # Variable to keep track of the length
    # of the longest common sub sequence
    maxLen = 0
 
    # position array to keep track
    # of position of elements
    # in each permutation
    pos = [0] * k
    for i in range(len(pos)):
        pos[i] = [0] * n
 
    # Array to store the length of LCS
    dp = [0] * n
 
    for i in range(k):
        for j in range(n):
            pos[i][arr[i][j] - 1] = j
 
    # Loop to calculate the LCS
    # of all the permutations
    for i in range(n):
        dp[i] = 1
        for j in range(i):
            good = True
            for p in range(k):
                if (pos[p][arr[0][j] - 1] > pos[p][arr[0][i] - 1]):
                    good = False
                    break
            if (good):
                dp[i] = max(dp[i], 1 + dp[j])
                maxLen = max(maxLen, dp[i])
    return maxLen
 
# Driver code
arr = [[2, 5, 1, 4, 6, 3], [5, 1, 4, 3, 2, 6], [5, 4, 2, 6, 3, 1]]
N = len(arr[0])
K = 3
 
# Function Call
print(findLcs(arr, N, K))
 
# This code is contributed by Saurabh Jaiswal

C#

// C# code to find the longest common
// sub sequence of k permutations.
using System;
 
class GFG {
 
    // Function to find the longest common
    // sub sequence of k permutations.
    static int findLcs(int[, ] arr, int n, int k)
    {
        // Variable to keep track of the length
        // of the longest common sub sequence
        int maxLen = 0;
 
        // position array to keep track
        // of position of elements
        // in each permutation
        int[, ] pos = new int[k, n];
 
        // Array to store the length of LCS
        int[] dp = new int[n];
 
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < n; j++) {
                pos[i, arr[i, j] - 1] = j;
            }
        }
 
        // Loop to calculate the LCS
        // of all the permutations
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                bool good = true;
                for (int p = 0; p < k; p++) {
                    if (pos[p, arr[0, j] - 1]
                        > pos[p, arr[0, i] - 1]) {
                        good = false;
                        break;
                    }
                }
                if (good) {
                    dp[i] = Math.Max(dp[i], 1 + dp[j]);
                    maxLen = Math.Max(maxLen, dp[i]);
                }
            }
        }
        return maxLen;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int[, ] arr = { { 2, 5, 1, 4, 6, 3 },
                        { 5, 1, 4, 3, 2, 6 },
                        { 5, 4, 2, 6, 3, 1 } };
        int N = arr.GetLength(1);
        int K = 3;
 
        // Function Call
        Console.WriteLine(findLcs(arr, N, K));
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
       // JavaScript code for the above approach
 
       // Function to find the longest common
       // sub sequence of k permutations.
       function findLcs(arr, n, k) 
       {
        
           // Variable to keep track of the length
           // of the longest common sub sequence
           let maxLen = 0;
 
           // position array to keep track 
           // of position of elements 
           // in each permutation
           let pos = new Array(k);
           for (let i = 0; i < pos.length; i++) {
               pos[i] = new Array(n)
           }
 
           // Array to store the length of LCS
           let dp = new Array(n);
 
           for (let i = 0; i < k; i++) {
               for (let j = 0; j < n; j++) {
                   pos[i][arr[i][j] - 1] = j;
               }
           }
 
           // Loop to calculate the LCS 
           // of all the permutations
           for (let i = 0; i < n; i++) {
               dp[i] = 1;
               for (let j = 0; j < i; j++) {
                   let good = true;
                   for (let p = 0; p < k; p++) {
                       if (pos[p][arr[0][j] - 1]
                           > pos[p][arr[0][i] - 1]) {
                           good = false;
                           break;
                       }
                   }
                   if (good) {
                       dp[i] = Math.max(dp[i], 1 + dp[j]);
                       maxLen = Math.max(maxLen, dp[i]);
                   }
               }
           }
           return maxLen;
       }
 
       // Driver code
       let arr =
           [[2, 5, 1, 4, 6, 3],
           [5, 1, 4, 3, 2, 6],
           [5, 4, 2, 6, 3, 1]];
       let N = arr[0].length;
       let K = 3;
 
       // Function Call
       document.write(findLcs(arr, N, K));
 
 // This code is contributed by Potta Lokesh
   </script>

Output

Time Complexity: O(N² * K)
Auxiliary Space: O(N * K)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!