Longest common subsequence withpermutations

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

Examples

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)

Algorithm

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++)
    {
        count1[string1[i]-'a']++;
    }
    //store characters count in array count2 for string2
    for (int i=0; i<string2.length(); i++)
    {
        count2[string2[i]-'a']++;
    }
 
    //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
    cout<<output;
}
 
//Main function
int main()
{
    string string1 = "hello", string2 = "hole";
    cout<<"Final output is: ";
    LCSOFpermutations(string1, string2);
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top