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.