An optimal solution would be something like
- create an array of 26 or 52 bytes depending on whether this is case sensitive
- iterate over the string and set the byte corresponding to each letter’s position in the alphabet to 1
- iterate over the byte array and for each 1 you encounter print out the corresponding letter
Consider the input “ba”
This solution will return “ab”, which is not a strong that can be generated by deleting characters from the input.
But that's what "lexicographical" means?
> In mathematics, the lexicographical order is a generalization of the way words are alphabetically ordered based on the alphabetical order of their component letters.
> This generalization consists primarily in defining a total order on the sequences (often called strings in computer science) of elements of a finite totally ordered set, often called an alphabet.
No. Please re-read the problem statement. It's way more complicated than that. If you figure out how to do it, try to figure out how to do it in O(N).