/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
private static boolean inSet(int set, char ch) {
return (set & (1 << (ch - 'a'))) != 0;
}
private static boolean includes(int set, int subset) {
return (set | subset) == set;
}
private static int addToSet(int set, char ch) {
return set | (1 << (ch - 'a'));
}
private static int removeFromSet(int set, char ch) {
return set & ~(1 << (ch - 'a'));
}
StringBuilder result = new StringBuilder();
int[] subsets = new int[s.length()];
int subset = 0;
for (int i = s.length() - 1; i >= 0; i--) {
char ch = s.charAt(i);
subset = addToSet(subset, ch);
subsets[i] = subset;
}
int curPos = 0;
while (subset != 0) {
for (char ch = 'a'; ch <= 'z'; ++ch) {
if (inSet(subset, ch)) {
int charpos = s.indexOf(ch, curPos);
if (includes(subsets[charpos], subset)) {
result.append(ch);
subset = removeFromSet(subset, ch);
curPos = charpos + 1;
break;
}
}
}
}
return result.toString();
}
{
Scanner sc
= new Scanner
(System.
in); while (sc.hasNext()) {
System.
out.
println(removeDuplicateLetters
(s
)); }
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXByaXZhdGUgc3RhdGljIGJvb2xlYW4gaW5TZXQoaW50IHNldCwgY2hhciBjaCkgewoJICAgIHJldHVybiAoc2V0ICYgKDEgPDwgKGNoIC0gJ2EnKSkpICE9IDA7ICAgIAoJfQoJCglwcml2YXRlIHN0YXRpYyBib29sZWFuIGluY2x1ZGVzKGludCBzZXQsIGludCBzdWJzZXQpIHsKCSAgICByZXR1cm4gKHNldCB8IHN1YnNldCkgPT0gc2V0OwoJfQoJCglwcml2YXRlIHN0YXRpYyBpbnQgYWRkVG9TZXQoaW50IHNldCwgY2hhciBjaCkgewoJICAgIHJldHVybiBzZXQgfCAoMSA8PCAoY2ggLSAnYScpKTsKCX0KCQoJcHJpdmF0ZSBzdGF0aWMgaW50IHJlbW92ZUZyb21TZXQoaW50IHNldCwgY2hhciBjaCkgewoJICAgIHJldHVybiBzZXQgJiB+KDEgPDwgKGNoIC0gJ2EnKSk7IAoJfQoJCglwdWJsaWMgc3RhdGljIFN0cmluZyByZW1vdmVEdXBsaWNhdGVMZXR0ZXJzKFN0cmluZyBzKSB7CgkgICAgU3RyaW5nQnVpbGRlciByZXN1bHQgPSBuZXcgU3RyaW5nQnVpbGRlcigpOwoJICAgIGludFtdIHN1YnNldHMgPSBuZXcgaW50W3MubGVuZ3RoKCldOwoJCgkgICAgaW50IHN1YnNldCA9IDA7CgkgICAgZm9yIChpbnQgaSA9IHMubGVuZ3RoKCkgLSAxOyBpID49IDA7IGktLSkgewoJICAgICAgICBjaGFyIGNoID0gcy5jaGFyQXQoaSk7CgkgICAgICAgIHN1YnNldCA9IGFkZFRvU2V0KHN1YnNldCwgY2gpOwoJICAgICAgICBzdWJzZXRzW2ldID0gc3Vic2V0OwoJICAgIH0KCQoJICAgIGludCBjdXJQb3MgPSAwOwoJICAgIHdoaWxlIChzdWJzZXQgIT0gMCkgewoJICAgICAgICBmb3IgKGNoYXIgY2ggPSAnYSc7IGNoIDw9ICd6JzsgKytjaCkgewoJICAgICAgICAgICAgaWYgKGluU2V0KHN1YnNldCwgY2gpKSB7CgkgICAgICAgICAgICAgICAgaW50IGNoYXJwb3MgPSBzLmluZGV4T2YoY2gsIGN1clBvcyk7CgkgICAgICAgICAgICAgICAgaWYgKGluY2x1ZGVzKHN1YnNldHNbY2hhcnBvc10sIHN1YnNldCkpIHsKCSAgICAgICAgICAgICAgICAgICAgcmVzdWx0LmFwcGVuZChjaCk7CgkgICAgICAgICAgICAgICAgICAgIHN1YnNldCA9IHJlbW92ZUZyb21TZXQoc3Vic2V0LCBjaCk7CgkgICAgICAgICAgICAgICAgICAgIGN1clBvcyA9IGNoYXJwb3MgKyAxOwoJICAgICAgICAgICAgICAgICAgICBicmVhazsKCSAgICAgICAgICAgICAgICB9CgkgICAgICAgICAgICB9CgkgICAgICAgIH0KCSAgICB9CgkKCSAgICByZXR1cm4gcmVzdWx0LnRvU3RyaW5nKCk7IAoJfQkKCQoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBqYXZhLmxhbmcuRXhjZXB0aW9uCgl7CgkJU2Nhbm5lciBzYyA9IG5ldyBTY2FubmVyKFN5c3RlbS5pbik7CgkJd2hpbGUgKHNjLmhhc05leHQoKSkgewoJCQlTdHJpbmcgcyA9IHNjLm5leHQoKTsKCQkJU3lzdGVtLm91dC5wcmludGxuKHJlbW92ZUR1cGxpY2F0ZUxldHRlcnMocykpOwoJCX0KIAl9Cn0=