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