## 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)

## Reply