Unique SubString
While Safae is working on controlling the world using her raspberries, her sister Ibtissam decided to pay her a visit. Ibtisam has a high level of curiosity which pushed Safae to secure the refrigerator where she keeps the berries using a password.
Ibtissam knows her sister's weird password choices:
* Safae does not use a letter more than once in all her passwords.
* She also uses lexicologically small passwordsIbtissam does not have the intention of messing with her sister's work, she just wants to have a look at the content of the refrigerator.
Your task is to help Ibtissam find the password of her sister's refrigerator by removing duplicate letters from a given string to obtain Safae's password. You have to make sure the resulting string is the lexicographically smallest one.
Note that you are not allowed to change the characters order in the given string and all the characters appearing int he given string must appear in the password exactly once.
Input Specification
The Input consists of a single String s of length |s| where \(1 \le |s| \le 10^5\). The String s consists of only lower case characters ('a' to 'z').
Output Specification
Output a single line contains the answer to the problem.
Sample Input
acbaSample Output
acbSample Input
bcacbacSample Output
abcNotes
In the first sample, you cannot remove the 2nd letter 'c' since it appears only once.
Comments
nvrmnd I got the answer!
why the answer of the first sample is "acb" and not "ab" ?
why in the second example the output is abc and not bca
You need to find the lexicologically smallest string .