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