# Longest Common Subsequence with Permutations

Difficulty Level Easy
Permutation String

## 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 = {0};
int count2 = {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;
int count2[] = new int;
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”.