I've just finished the 2nd year of my CS degree. In about 3 minutes I came up with:
1) create an empty string, call it "S2"
2) loop over each char in original string
3) if the char isn't in S2, add it to the end of S2. If the char is already present in S2 then lexicographically compare the prior S2 verse S2 with this char shifted to the end. Keep the lower ordered one.
This took about 3-4 minutes of thinking and is O(n). It might not be optimal, it might not even be a correct solution as I've spent only a few minutes on it. However, I feel it's close and it wouldn't take much to flesh out.
1) create an empty string, call it "S2" 2) loop over each char in original string 3) if the char isn't in S2, add it to the end of S2. If the char is already present in S2 then lexicographically compare the prior S2 verse S2 with this char shifted to the end. Keep the lower ordered one.
This took about 3-4 minutes of thinking and is O(n). It might not be optimal, it might not even be a correct solution as I've spent only a few minutes on it. However, I feel it's close and it wouldn't take much to flesh out.
EDIT: This solution is incorrect.