Here's what I came up with after experimenting with handling the leetcode example ("given cbacdcbc, produce acdb") manually:

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.

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.

That solution as written is O(n^3)

This is not an easy problem.

You only check each character in the string once. A hashmap can check if the char is used already.

For each char in the original string there is: * 1 check in hashmap (let's assume it was found). This is O(1) * build a new string where we remove that char from the string we are building (string2) and add it to the end. This step may look O(n) initially since we need to find that char in string2 but string2 is capped at 26 characters so it's O(1) * One comparison between the string we are building and the altered version.

How does that make it O(n^3)? I can't see which step inside the initial loop is O(n) or greater.

EDIT: The solution is actually incorrect so this is now semantics.

> EDIT: The solution is actually incorrect so this is now semantics.

Interesting use of "semantics".

The question of "how fast does this algorithm run?" is totally independent from the question of "what does this algorithm do?"; the second one is semantic but you're discussing the first here.

The algorithm I described was O(n), you said it was O(3). I'm assuming this happened because my algorithm was actually an incorrect solution but you subconsciously added in steps to make it a correct algorithm which changed its complexity. Hence it's semantics because we seem to be discussing two different algorithms.

Can I ask about the suffix tree solution? A one-hour problem is still pretty easy in the grand scheme of things.

input: "bcabc"

  1. "b"
  2. "bc"
  3. "bca"
  4. "bca"
  5. "bca"

What am I missing?

Take all the possible answers with duplicates removed, and return the first one in alphabetical order.

input: "bcabc"

output: "abc"

Nothing. I hadn't fleshed out my idea yet and that's the error I thought could exist. My solution is wrong.

that is a single line of code in javascript, assuming you just want the value in #5 const foo = [...new Set('bcabc'.split(''))].join('')