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

```

## Problem: Max and Min Products

*Difficulty: Easy

Given a set, we need to find maximum and minimum possible product among all subsets of the set.
Examples:

```Input : arr[] = {4, -2, 5};
Output: Maximum product = 20
Minimum product = -40
Maximum product is obtained by multiplying
4 5
Minimum product is obtained by multiplying
4, -2, 5

Input : arr[] = {-4, -2, 3, 7, 5, 0, 1};
Output: Maximum product = 840
Minimum product = -420
Maximum product is obtained by multiplying
-4, -2, 3, 7, 5
Minimum product is obtained by multiplying
-4, 3, 7,```

Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated denoting the elements of the array.

Output:
Print the maximum product followed by a space followed by minimum subset product.

Constraints:
1 ≤ T ≤ 40
1 ≤ N ≤ 20
-100 ≤ A[i] <= 100

Example:
Input
2
3
1 2 3
4
-1 -2 -3 -4

Output

6 1
24 -24

```"""
@autho: loctv
@time: 09:52PM January 4, 2017
"""
import itertools
import operator

def all_sub_sets(l):
"""
generate all sub sets (with length 1,2,3,....n)
l: list of numbers
"""
bound = len(l)
for i in range(1, bound+1):
yield itertools.combinations(l, i)

def max_min_products(l):
"""
find max and min product from all sub sets
l: list of numbers
"""
max_product, min_product = -100**20, 100**20
for sub_sets in all_sub_sets(l):
for sub_set in sub_sets:
product = reduce(operator.mul, sub_set)
if product > max_product:
max_product = product
if product < min_product:
min_product = product
print max_product, min_product

if __name__ == '__main__':
t = input()
for _ in range(t):
n = input()
l = map(int, raw_input().strip().split())
max_min_products(l)

```

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r