Java remove duplicate characters(included) from a given String

Question

Is there any efficient way (that not includes "contains" or "indexOf" methods) to remove duplicate characters (included) from a given String.

For example:

input: "abcdcb" output: "ad"

input: "abracadabra" output: "cd"

I have tried using RegEx but something got wrong:

public static String function(String str) {
    return str.replaceAll("([a-z]+)\\1", "");
}

Edit: Longest, non efficient solution:

public static String function(String s) {
    String result = "";

    for (int i = 0; i < s.length(); i++)
        if(s.length() - s.replace("" + s.charAt(i), "").length() == 1)
            result += "" + s.charAt(i);
    
    return result;
}

Create a Map<Character, Integer> in which you will store how many times each character appeared. Then only collect those which appeared once. — Pshemo
– Pshemo, Commented Jun 25, 2022 at 19:16

VGR · Accepted Answer · 2022-06-25 20:05:44Z

6

A single regular expression cannot do this.

As Pshemo suggested, create a Map that counts the character occurrences:

Map<Integer, Long> codePointCounts = s.codePoints().boxed().collect(
    Collectors.groupingBy(
        c -> c, LinkedHashMap::new, Collectors.counting()));

(Using LinkedHashMap will preserve the order of the code points when they are placed in the Map.)

Then discard all the Map entries which don’t have a count of one:

codePointCounts.values().retainAll(Set.of(1L));

Removing a Map value will remove its corresponding key, so any remaining Map keys are unique codepoints from the original String. You can create a String from an array of ints:

int[] codePoints = codePointCounts.keySet().stream()
    .mapToInt(Integer::intValue).toArray();

String uniqueChars = new String(codePoints, 0, codePoints.length);

answered Jun 25, 2022 at 20:05

VGR

44.9k4 gold badges52 silver badges71 bronze badges

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

2 Comments

Mabadai Over a year ago

Thanks for your answer. It stays O(1) or there will be collisions while removing the keys?

Cheng Thao Over a year ago

It's not O(1) because it has to visit all the characters in the string. So, it is O(n). The hash map still gives approximately O(1) even with collisions.

Cheng Thao · Accepted Answer · 2022-06-26 02:09:17Z

3

Here's another approach. I map characters to indices of an int array. The array is used to count the number of times a character appears in the string. If the count is zero, then it is the first time it's seen and so it's added to the char array r. At the end, we return a string constructed from the char array r.

    public static String function(String s) {
        int[]  a = new int[27];
        char[] r = new char[s.length()];
        int len = 0;
        for(int i=0; i<s.length(); i++)
            if (a[s.charAt(i)-'a']++ ==0) 
               r[len++] = s.charAt(i);
        return new String(r, 0, len);
    }

answered Jun 26, 2022 at 2:09

Cheng Thao

1,4931 gold badge5 silver badges9 bronze badges

Comments

Sayan Bhattacharya · Accepted Answer · 2022-06-26 06:42:12Z

2

Using VGR's approach but only using java.util.stream

String value="abracadabra";             

String uniqueChars = Arrays.asList(value.split(""))   //creating a list from String
        .stream()
        .collect(Collectors.groupingBy(s->s,LinkedHashMap::new, Collectors.counting())) // grouping by all values with their no of occurrences(as count)
        .entrySet() //after creating the map traversing through the entryset 
        .stream()
        .filter(m->m.getValue()==1L) // fetch values which have count=1
        .map(Map.Entry::getKey) 
        .collect(Collectors.joining());

System.out.println(uniqueChars);
//output = cd

answered Jun 26, 2022 at 6:42

Sayan Bhattacharya

1,3681 gold badge6 silver badges14 bronze badges

Collectives™ on Stack Overflow

Java remove duplicate characters(included) from a given String

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related