Remove duplications from a Java String

Question

today I tackled this coding challenge: Remove duplications from string. I was thinking of either using a Hashmap or a Set but realized that a set might have a longer run time since the way it determines if a numbers is in there or not is by traversing each element. This lead me to use a hashmap instead. I have not taken care of any edge cases but wanted to get people's opinion of this implementation. From what I understand this would be a \$O(n)\$, (\$n\$ being the length of the input String), correct?

  String test = "Banana";
    HashMap<Character, String> nodups = new HashMap<>();
    for(int i = 0; i < test.length();i++){
        nodups.put(test.charAt(i),String.valueOf(test.charAt(i)));
    }

    StringBuilder noDupsString = new StringBuilder();
    for(Character key : nodups.keySet()){
        noDupsString.append(nodups.get(key));
    }

    System.out.println("String value with no dups :" + noDupsString);
}

One problem with using HashMap is that there is no guarantee of the order of the results. Not sure if order of letters is important, but your program outputs "aBn" — mcgyver5
– mcgyver5, Commented Jun 29, 2017 at 21:10
A LinkedHashSet will remove duplicates and keep results in order — mcgyver5
– mcgyver5, Commented Jun 29, 2017 at 21:47

Vogel612 · Accepted Answer · 2017-06-29 21:12:56Z

Soo.. let me tell you a secret about Java's HashSet...

This class implements the Set interface, backed by a hash table (actually a HashMap instance)

to cut the chase short: you could've just used a HashSet, it would've been at worst equally slow.

now to review the code... Since you don't make any guarantees for execution order in your code, neither will I:

System.out.println("String value with no duplicates: " 
    + new HashSet<>(Arrays.asList(test.toCharArray())).stream().collect(Collectors.joining("")));

It should be acceptably easy to see, that this is horrendous code, but it does the same thing as your code...

Either way, the code presented also has some issues:

Unnecessary creation of (relatively speaking) expensive objects.
String.valueOf(test.charAt(i)) is just bad form
Strangely hidden complexity.
In nodups.put(..) there's a hideous hidden complexity. You're hashing the character (which basically just turns it into an int and does some modulo calculations) and then put the char into it's place.
Double loop, where one is sufficient.
Currently the code does two loops, where one is sufficient. In a HashSet the contains-operation is \$\mathcal{O}(1)\$. This allows you to just collapse the loops instead of repeatedly overwriting the same value:
```
Set<Character> knownChars = new HashSet<>();
StringBuilder nodupsString = new StringBuilder();
for (Character c : test.toCharArray()) {
    if (!knownChars.contains(c)) {
        knownChars.add(c);
        nodupsString.append(c);
    }
}
```
This reduces the mathematical complexity from \$\mathcal{O}(2n)\$ to \$\mathcal{O}(n)\$. And don't come with the "constants are ignored in O-notation" fallacy. The problem is that too many people think that and as a result write badly performing code, which they think can't be made faster ... </rant>

Aside from that ... good job, I guess?

Thanks for you input I have learned something new and just improved my code. — TheLearner
– TheLearner, Commented Jun 29, 2017 at 23:56

jbw · Accepted Answer · 2017-06-30 20:16:39Z

1

Arrays.asList(test.toCharArray())

gives a List of char[] since toCharArray() gives a char[] and generics can not handle primitives.

String nodup = test.chars()
            .distinct()
            .mapToObj(i -> (char) i)
            .map(String::valueOf)
            .collect(Collectors.joining());

Or if HashSet should do the distinct:

List<Character> chars = test.chars()
            .distinct()
            .mapToObj(i -> (char) i)
            .collect(Collectors.toList());

String nodup = new HashSet<>(chars)
            .stream()
            .map(String::valueOf)
            .collect(Collectors.joining());

answered Jun 30, 2017 at 20:16

jbw

211 silver badge1 bronze badge

\$\begingroup\$ You could collapse the mapToObj and map calls into 1 mapToObj call by doing the int-to-char-to-String conversion in one function like mapToObj(x -> "" + (char)x) or similar. Also specify that this solution requires Java 8. \$\endgroup\$

Tamoghna Chowdhury
– Tamoghna Chowdhury

2017-07-02 06:06:37 +00:00
Commented Jul 2, 2017 at 6:06

Add a comment |

Stack Exchange Network

Remove duplications from a Java String

2 Answers 2

You must log in to answer this question.

Linked

Hot Network Questions

Remove duplications from a Java String

2 Answers 2

You must log in to answer this question.

Linked

Related

Hot Network Questions