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