1. When adding a letter to the suffix tree, skip any paths that already contain that letter. (Thus, each path will contain a given letter no more than once.)
2. Include accounting information in each node specifying the length of the longest suffix including that node.
From wikipedia, construction of an ordinary suffix tree takes time and space linear in the length of the input string. At this level of analysis, I'm just hoping that modification #2 doesn't affect that. #1 certainly won't, in that it involves spending less time and less space than otherwise (by bailing out early under some circumstances).
Once the tree is constructed, just walk it, selecting at every point the child that is lexicographically earliest among all children with the maximum suffix length.
Observation: constructing this tree by hand really feels exponential; I suspect that the linear time and space requirements lean on an assumption that the size of the alphabet is finite.
Observation #2: Based on the comment timestamps, this took about 40 minutes of thinking. I think it's a good solution, but it probably wouldn't look great in an interview. (Also, handwaving "construct a suffix tree" is fast, but actually producing the code to do it takes extra time.) :/
Observation #3: assuming your solution is correct, it is essentially a reduction by dynamic programming of this one, only doing the calculations that are necessary to produce the lexicographically earliest string where I produce them all.
After playing with suffix trees a little more, I need to make a correction:
This problem asks for subsequences rather than substrings. As a result, when adding a node to the "suffix tree", it will need to be added as the child of more nodes than it would if we were building an actual suffix tree.
This seems like the type of change that might make construction of the tree harder than O(n). In particular, it will violate the constraint that a suffix tree for a string of length n has only n leaves.
Build a suffix tree ( https://en.wikipedia.org/wiki/Suffix_tree ) of the input with two modifications:
1. When adding a letter to the suffix tree, skip any paths that already contain that letter. (Thus, each path will contain a given letter no more than once.)
2. Include accounting information in each node specifying the length of the longest suffix including that node.
From wikipedia, construction of an ordinary suffix tree takes time and space linear in the length of the input string. At this level of analysis, I'm just hoping that modification #2 doesn't affect that. #1 certainly won't, in that it involves spending less time and less space than otherwise (by bailing out early under some circumstances).
Once the tree is constructed, just walk it, selecting at every point the child that is lexicographically earliest among all children with the maximum suffix length.
Observation: constructing this tree by hand really feels exponential; I suspect that the linear time and space requirements lean on an assumption that the size of the alphabet is finite.
Observation #2: Based on the comment timestamps, this took about 40 minutes of thinking. I think it's a good solution, but it probably wouldn't look great in an interview. (Also, handwaving "construct a suffix tree" is fast, but actually producing the code to do it takes extra time.) :/
Observation #3: assuming your solution is correct, it is essentially a reduction by dynamic programming of this one, only doing the calculations that are necessary to produce the lexicographically earliest string where I produce them all.