Unique SubString

Submit solution

Points: 30
Time limit: 1.0s
Memory limit: 256M

Problem types

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 passwords

Ibtissam 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


Sample Output


Sample Input


Sample Output



In the first sample, you cannot remove the 2nd letter 'c' since it appears only once.


  • 0
    etheriousaad  commented on Jan. 19, 2021, 12:33 p.m.

    nvrmnd I got the answer!

  • 0
    etheriousaad  commented on Jan. 19, 2021, 12:28 p.m.

    why the answer of the first sample is "acb" and not "ab" ?

  • 0
    Soufiane_ELM  commented on Sept. 15, 2020, 1:49 p.m.

    why in the second example the output is abc and not bca

    • 0
      zakaF  commented on Sept. 16, 2020, 11:53 p.m.

      You need to find the lexicologically smallest string .