UVa 10252

From Algorithmist
Jump to navigation Jump to search

10252 - Common Permutation[edit]

Summary[edit]

Given two strings a and b, we have to find the largest string x such that there is a permutation of x that is a (not necessarily continuous) subsequence of a and another permutation of x (likely distinct) which is a subsequence of b. If there is more than one such string x, output the lexicographically smallest one.

Explanation[edit]

This problem is actually very easy to code, after you have a little bit of insight. Rather than considering the input strings as strings, consider them a multiset of characters. Let y be any string, and let Y be the multiset of characters produced from y. Suppose that Z is another multiset of characters. When can Z be ordered to get a subsequence of y? If some character occurs more times in Z than it does in Y, this is clearly impossible. In all other cases we can easily form the subsequence – take y and leave out some characters until all counts match.

Thus a string z can be permuted to obtain a subsequence of y if and only if Z is a subset (actually, a submultiset) of Y.

Now consider both strings a and b as multisets A and B. Let c be the string we seek, and C the corresponding multiset. We saw that C has to be a subset of both A and B. And as we want c to be as long as possible, C has to be the intersection of A and B. In other words, if a character occurs x times in a and y times in b, we may use it min(x,y) times in c.

To get the lexicographically smallest c, simply output C in sorted order.

Gotchas[edit]

  • There may be empty lines in the input.

Input[edit]

pretty
women
walking
down
the
street

thelineabovethisoneisblank
elementary
weatherreport

Output[edit]

e
nw
et

aeeert