4 ms·
> Let me give you and example of what I got at Google: [...] Solving this problem optimally with only what you remember from undergrad algo courses is impossibl
by krn 7y ago
> Let me give you and example of what I got at Google: [...] Solving this problem optimally with only what you remember from undergrad algo courses is impossible. You either need to have a knack for these types of challenges or solve enough of them to identify a solution pattern.
I have never tried to solve such problems before, but wouldn't it be enough to convert the string into a set of chars, then into an array of chars, sort it, and return it as a string?
- decebalus1 7y ago> wouldn't it be enough to convert the string into a set of chars, then into an array of chars, sort it, and return as a string? 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).
- mason55 7y agoThe proposed solution isn’t optimal but it works. Not sure what you think is wrong with it? 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
- jfk13 7y agoWon't that give you the letters in alphabetical order, which may not be correct? See example 2 on the problem page.
- krn 7y ago> Won't that give you the letters in alphabetical order, which may not be correct? 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. https://en.wikipedia.org/wiki/Lexicographical_order https://en.wikipedia.org/wiki/Lexicographical_order
- Twisol 7y agoI think the problem statement wants the lexicographically least string of those obtainable by deleting characters.
- mmierz 7y ago>The proposed solution isn’t optimal but it works. Not sure what you think is wrong with it? Consider the input “ba” This solution will return “ab”, which is not a strong that can be generated by deleting characters from the input.
- deleted 7y ago[deleted]