Remove duplicates without using additional buffer

Question

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);
    }

}

Can you give us the test case? what are the parameters used and what is the expected return plz? — TheEwook
– TheEwook, Commented Apr 2, 2013 at 16:09
this seems more appropriate for codereview.stackexchange.com — mothmonsterman
– mothmonsterman, Commented Apr 2, 2013 at 16:09

anubhava · Accepted Answer · 2013-04-02 16:26:13Z

2

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

answered Apr 2, 2013 at 16:26

anubhava

790k67 gold badges603 silver badges671 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Heng Over a year ago

if it wants to retain the char appeared the first time and take out the same char which appeared another time, how to do it

anubhava Over a year ago

Sorry didn't understand, can you clarify with an example?

Heng Over a year ago

okay, it works. if I type in "appropriate", the result is "opriate". However, if i want each char occurs only once and the result is "aproite", how to do it use the regex

anubhava Over a year ago

opriate also has each character only once but at different position. Feel free to post a new question if you want a different behavior.

1218985 · Accepted Answer · 2013-04-02 16:14:25Z

0

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));
        }
    }

answered Apr 2, 2013 at 16:14

1218985

8,1122 gold badges29 silver badges33 bronze badges

Comments

Vishal K · Accepted Answer · 2013-04-02 16:33:16Z

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);
    }

assafmo · Accepted Answer · 2013-04-02 16:36:42Z

0

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.

edited Apr 2, 2013 at 16:36

answered Apr 2, 2013 at 16:23

assafmo

1,0963 gold badges15 silver badges34 bronze badges

Comments

Marcello Grechi Lins · Accepted Answer · 2016-06-23 02:10:39Z

0

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.

answered Jun 23, 2016 at 2:10

Marcello Grechi Lins

3,4088 gold badges40 silver badges72 bronze badges

Collectives™ on Stack Overflow

Remove duplicates without using additional buffer

5 Answers 5

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

4 Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

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

4 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related