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,aandb, print the longest stringxof lowercase letters such that there is a permutation ofxthat is a subsequence ofaand there is a permutation ofxthat is a subsequence ofb. If severalxsatisfy 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
```

## Comments