Earlier quoted context omitted.
> 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 o…
> 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).
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