Longest common subsequence withpermutations

Find the longest string whose permutations are sub-sequences of given two strings. Output longest must be sorted.


Input strings : s1: “hello”, s2: “hole”

Output : ehlo
Here, permutation of ehlo is subsequence of hello, hole. (sorted and longest)

Time complexity : O(m + n)


1. Create two arrays count1 and count2.

2. Count1 stores the count of characters in string1 and count2 stores the count of characters in string2.

3. Append character ‘c’ by min(count1[‘c’], count2[‘c’]) times into the result.

4. Do this for all characters in lexicographic order.

5. Return the final result.

C++ Program

#include <bits/stdc++.h>
using namespace std;

//LCS --> longest common sub-sequence
void LCSOFpermutations(string string1, string string2)
    int count1[26] = {0}, count2[26]= {0};
    //store characters count in array count1 for string1
    for (int i=0; i<string1.length(); i++)
    //store characters count in array count2 for string2
    for (int i=0; i<string2.length(); i++)
    //Traverse both arrays
    //append character 'a'+ i min(count1[i],count2[i]) times
    string output;
    for (int i=0; i<26; i++)
        for (int j=1; j<=min(count1[i],count2[i]); j++)
            output.push_back('a' + i);
    //return final output
//Main function
int main()
    string string1 = "hello", string2 = "hole";
    cout<<"Final output is: ";
    LCSOFpermutations(string1, string2);
    return 0;

Try It


Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions