package com.vav.CTCI.Chapter1;

import java.util.Arrays;

/**
 * Created by Vaibhav on 4/24/17.
 */
public class QX_RemoveDuplicates {
    public static void main(String arg[]){
        System.out.println(removeDuplicatesBF(new String("testeddbybxx")));
    }
    //1. Replacing the last character with duplicates O(n2), only replaces duplicates not triples or more
    public static String removeDuplicatesBF(String str){
        char[] chars = str.toCharArray();
        int length = str.length();
        char temp;

        for(int i=0;i<chars.length-1;i++){
            for(int j=chars.length-1;j>i;){
                if(chars[i]==chars[j]){
                    --length;
                    temp=chars[j];
                    chars[j]=chars[length];
                    chars[length]=temp;
                }
                --j;
            }
        }
        return new String(chars).substring(0,length);
    }
    //2. Sorting and then replacing last chars with duplicates O(nlog(n))
    public static String removeDuplicatesSorting(String str){
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        int length = str.length();
        char temp;
        int i=0;
        for(int j=1;j<chars.length-1;j++){
            if(chars[i]!=chars[j]){
               i++;
               chars[i]=chars[j];

            }
        }
        return new String(chars).substring(0,i+1);
    }
    //3. Remove duplicates using hashmaps O(n)

}

@@ -49,16 +49,74 @@
 .Arrays;
+%0Aimport java.util.Enumeration;%0Aimport java.util.Hashtable;
 %0A%0A/**%0A *
@@ -305,16 +305,205 @@
 xx%22)));%0A
+        Enumeration%3CCharacter%3E en = removeDuplicatesHashmaps(new String(%22testeddbybxx%22));%0A        while(en.hasMoreElements())%7B%0A            System.out.print(en.nextElement()+%22-%22);%0A        %7D%0A
     %7D%0A  
@@ -1698,11 +1698,362 @@
 ps O(n)%0A
+    private static Enumeration removeDuplicatesHashmaps(String s) %7B%0A        char%5B%5D chars = s.toCharArray();%0A        Hashtable hashtable = new Hashtable();%0A        for(int i=0;i%3Cchars.length;i++)%7B%0A            if(!hashtable.containsKey(chars%5Bi%5D))%7B%0A                hashtable.put(chars%5Bi%5D,0);%0A            %7D%0A        %7D%0A        return hashtable.keys();%0A    %7D
 %0A%7D%0A

Remove dups hashing