From the first look it really smells like a complicated dynamic programming algorithm but we need to have a deeper look to understand the difficulty of this task. Here is what the task wants from us: find a string x that a permutation of x will be a subsequence of s1 and s2. Subsequence means that the letters should exist on those strings s1 and s2 and every other letter must be on the right than the previous one (they don't have to be consequetive) . This would be a dynamic programming task if there wasn't the phrase "one permutation of x". Let me demonstrate with an example. CgrAyuT
(I made some letters uppercase for clarity). So , if we have an X="CAT" than it can be considered as a subsequence of the given string but x="TAC", can't , but we are free to take any permutation of X we want so we will move the elements and form the word "CAT" and check. So, the answer is simple, it will be just a string which contains all the letters which both of the strings contain. It can be found easily in O(s.size()^2) time which is enough. NOTE don't forget to sort the final answer because the problem requires the first answer in alphabetical order.
No comments:
Post a Comment