fork(5) download
copy 
  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
comments (?)
stdin
copy 
bcabc
cbacdcbc
stdout
copy 
abc
acdb
https://ideone.com/wIKi3x
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!