fork(4) download
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. private static boolean inSet(int set, char ch) {
  11. return (set & (1 << (ch - 'a'))) != 0;
  12. }
  13.  
  14. private static boolean includes(int set, int subset) {
  15. return (set | subset) == set;
  16. }
  17.  
  18. private static int addToSet(int set, char ch) {
  19. return set | (1 << (ch - 'a'));
  20. }
  21.  
  22. private static int removeFromSet(int set, char ch) {
  23. return set & ~(1 << (ch - 'a'));
  24. }
  25.  
  26. public static String removeDuplicateLetters(String s) {
  27. StringBuilder result = new StringBuilder();
  28. int[] subsets = new int[s.length()];
  29.  
  30. int subset = 0;
  31. for (int i = s.length() - 1; i >= 0; i--) {
  32. char ch = s.charAt(i);
  33. subset = addToSet(subset, ch);
  34. subsets[i] = subset;
  35. }
  36.  
  37. int curPos = 0;
  38. while (subset != 0) {
  39. for (char ch = 'a'; ch <= 'z'; ++ch) {
  40. if (inSet(subset, ch)) {
  41. int charpos = s.indexOf(ch, curPos);
  42. if (includes(subsets[charpos], subset)) {
  43. result.append(ch);
  44. subset = removeFromSet(subset, ch);
  45. curPos = charpos + 1;
  46. break;
  47. }
  48. }
  49. }
  50. }
  51.  
  52. return result.toString();
  53. }
  54.  
  55. public static void main (String[] args) throws java.lang.Exception
  56. {
  57. Scanner sc = new Scanner(System.in);
  58. while (sc.hasNext()) {
  59. String s = sc.next();
  60. System.out.println(removeDuplicateLetters(s));
  61. }
  62. }
  63. }
Success #stdin #stdout 0.06s 4386816KB
stdin
bcabc
cbacdcbc
stdout
abc
acdb