A very short post for today, based on the following problem which is on the UVA Online Judge website. The problem is of course rather simple but I was somewhat impressed by how short the solution ended up being in Python so I decided to write a post on it. First the problem statement:

Given two strings of lowercase letters, a and b, print the longest string x of lowercase letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b. If several x satisfy the criteria above, choose the first one in alphabetical order. Example: given "the" and "street" output "et".

After looking at the problem for a few minutes it is easy to see that it is essentially the same as a multi-set intersection operation. Remembering that Python's collections.Counter is a versatile multi-set implementation, we can solve this problem in basically one line in Python:

from collections import Counter

def common_permutation(a, b):
    return ''.join(k * v for k, v in sorted((Counter(a) & Counter(b)).items()))

print common_permutation('pretty', 'women')
print common_permutation('walking', 'down')
print common_permutation('the', 'street')
print common_permutation('aaabbbbccdddddd', 'bbdddcccaaaaaaadd')
print common_permutation('bbdddcccaaaaaaadd','aaabbbbccdddddd')

And the output:

e
nw
et
aaabbccddddd
aaabbccddddd