CODEWITHSUNDEEP
javaduplicates
Learner
Learner

Reputation: 2339

Remove duplicates without using additional buffer

I wrote a simple program to remove duplicates from a String without using any additional buffers. Can someone let me know if this is a good solution? I just want to know if there is any other solution better than the below solution..

Edit: If I pass in 'Follow Up' as input, I should get back the unique String 'FW UP'

    public static void removeDuplicateString(String input) {
        String value1 = input;
        String value2 = input;
        String finalValue = "";
        int count = 0;
        char char1;
        char char2;
        for (int i = 0; i < value1.length(); i++) {
            char1 = value1.charAt(i);
            for (int j = 0; j < value2.length(); j++) {
                char2 = value2.charAt(j);
                if (char1 == char2) {
                    count++;
                }
            }
            if (count > 1) {
                //System.out.println(i);
            } else {
                finalValue = finalValue + char1;
            }

            count = 0;
        }
        System.out.println(finalValue);
    }

}

Upvotes: 0

Views: 2331

Answers (5)

Marcello Grechi Lins
Marcello Grechi Lins

Reputation: 3410

You can use a "Mergesort" or a "Quicksort" (assuming you can use a temporary arry to allocate the data while you sort it, you would need an extra "O(n)" space for doing so).

Once you have the array sorted you can simply iterate through the array, comparing one element with the following, and everytime you find that a given element is equal to the same one, you shift the elements back one position.

By doing this you have :

  • O(N LOG N) because of the sort
  • O(N) to iterate through all the elements
  • O(M) to shift elements backwards

Depending on the number of duplicates this code can get really slow because of the cost of shifting elements backwards to erase the duplicates.

Upvotes: 0

assafmo
assafmo

Reputation: 1086

Your solution works.

Another solution:

public static void removeDuplicateString2(String input) {
    wh:
    while(true)
    {
        for(char c : input.toCharArray())
        {
            if(input.contains("" + c + c))
            {
                input = input.replaceAll("["+ c +"]" + "["+ c +"]", "");
                continue wh;
            }
        }
        break;
    }

    System.out.println(input);
}

Ugly but works.

Upvotes: 0

Vishal K
Vishal K

Reputation: 13066

public You can try this:

   public static void removeDuplicateString(String input) {
        char[] ch = input.toCharArray();
        char[] copy = new char[ch.length];
        char[] avoid = new char[ch.length];
        int counter = 0,count=0;
        for (int i = 0 ; i < ch.length; i++)
        {
            char cch = ch[i];
            boolean duplicate = false;
            if (input.indexOf(cch)==i && input.indexOf(cch,i+1)==-1)
            {
                for (int j = 0 ; j <=count ; j++)
                {
                    if (avoid[i]==cch)
                    {
                        duplicate = true;
                        break;
                    }
                }
                if (!duplicate)
                {
                    copy[counter] = cch;
                    counter++;
                }
            }
            else
            {
                avoid[count] = cch;
                count++;
            }
        }
        String finalString = new String(copy,0,counter);
        System.out.println(finalString);
    }

Upvotes: 0

anubhava
anubhava

Reputation: 785126

How about using a positive lookahead based regex like this to remove duplicate characters from a given String:

String nonDup = input.replaceAll("(.)(?=.*?\\1)", "");

Live Demo: http://ideone.com/W7EaPq

Upvotes: 2

1218985
1218985

Reputation: 8012

You can try this:

public String removeDuplicateChars(String inputString) {
        if (inputString.length() <= 1 ) {
            return inputString;
        }
        if(inputString.substring(1, 2).equals(inputString.substring(0, 1)) ) {
            return removeDuplicateChars(inputString.substring(1));
        } else {
            return inputString.substring(0, 1) + removeDuplicateChars(inputString.substring(1));
        }
    }

Upvotes: 0

Related Questions