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