Table of Contents
Problem Statement
In the “Longest Common Subsequence with Permutations” problem we have given two strings “s” and “t”. Find the longest string whose permutations are sub-sequences of the given two strings. Output longest must be sorted.
Input Format
The first line containing a string “s”.
The second line containing a string “t”.
Output Format
The first line only containing a string that represents the longest string whose permutations are sub-sequences of the strings “s” and “t”.
Example
hello hole
ehlo
Explanation: Here, the permutation of “ehlo” is the subsequence of hello, hole which is sorted and longest among all possible permutations.
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.
Implementation
C++ Program to find the Longest Common Subsequence with Permutations
#include <bits/stdc++.h> using namespace std; int main() { string s,t; cin>>s>>t; int count1[26] = {0}; int count2[26] = {0}; for (int i=0; i<s.length(); i++) { count1[s[i]-'a']++; } for (int i=0; i<t.length(); i++) { count2[t[i]-'a']++; } string ans; for(int i=0; i<26; i++) { for (int j=1;j<=min(count1[i],count2[i]); j++) { ans.push_back('a' + i); } } cout<<ans<<endl; return 0; }
Java Program to find the Longest Common Subsequence with Permutations
import java.util.Scanner; class sum { public static void main(String[] args) { Scanner sr = new Scanner(System.in); String s = sr.next(); String t = sr.next(); int count1[] = new int[26]; int count2[] = new int[26]; for(int i=0;i<26;i++) { count1[i]=0; count2[i]=0; } for (int i=0; i<s.length(); i++) { count1[s.charAt(i)-'a']++; } for (int i=0; i<t.length(); i++) { count2[t.charAt(i)-'a']++; } String ans=""; for(int i=0; i<26; i++) { for (int j=1;j<=Math.min(count1[i],count2[i]); j++) { ans+=(char)('a' + i); } } System.out.println(ans); } }
tutorialcup algorithm
ailort
Complexity Analysis to find the Longest Common Subsequence with Permutations
Time Complexity
O(n) where n is denoting the length of the maximum size string among “s” and “t”.
Space Complexity
O(n) because we store the final answer in a string. And the maximum length of the string is equal to n if both the string are equals.