## Problem: LCS with permutations

*Difficulty: Easy

Given two strings in lowercase, find the longest string whose permutations are subsequence of given two strings. The output longest string must be sorted.

Examples:

```Input  :  str1 = "pink", str2 = "kite"
Output : "ik"
The string "ik" is the longest sorted string
whose one permutation "ik" is subsequence of
"pink" and another permutation "ki" is
subsequence of "kite".

Input  : str1 = "working", str2 = "women"
Output : "now"

Input  : str1 = "geeks" , str2 = "cake"
Output : "ek"

Input  : str1 = "aaaa" , str2 = "baba"
Output : "aa"
```

Input:
First line of the input contains no of test cases  T, then T test cases follow. Each test case consist of 2 space separated integers n and m denoting the size of string str1 and str2 respectively. The next two lines contains the 2 string str1 and str2 .
Output:
For each test case print the output string in sorted order.
Constraints:
1 <= T <= 30
1 <= size(str1),size(str2)<= 100
Example:
Input:
2
6 6
abcdef
edgfhr
3 2
abc
ca

Output:
def
ac

Implementation: Python2.7

```"""
@author: loctv
@time: 11:04PM January 4, 2017
"""

#code
def frequency_of_chars_in(string):
"""
Calculate frequency of each characters in string
"""
d = {}
for c in string:
d[c] = d.setdefault(c, 0) + 1
return d

def lcs_with_permutations(string1, string2):
"""
Get LCS of string1 and string2 with permutations
Same as get all common characters of string1 and string2
"""
d_string1 = frequency_of_chars_in(string1)
d_string2 = frequency_of_chars_in(string2)
res = bytearray('')
for c in d_string1:
if c in d_string2 and d_string2[c]:
res.extend(c*min(d_string1[c], d_string2[c]))
d_string1[c] = 0 #mark as readed
d_string2[c] = 0 #mark as readed
for c in d_string2:
if c in d_string1 and d_string1[c]:
res.extend(c*min(d_string1[c], d_string2[c]))
d_string1[c] = 0 #mark as readed
d_string2[c] = 0 #mark as readed
#print the result in sorted order
print ''.join(sorted(list(str(res))))

if __name__ == '__main__':
t = input()
for _ in range(t):
size1, size2 = map(int, raw_input().strip().split())
string1 = raw_input().strip()
string2 = raw_input().strip()
lcs_with_permutations(string1, string2)

```
Advertisements