# Remove duplications from a Java String

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 Jun 29 '17 at 21:10
• Do you know how I could fix this ? – TheLearner Jun 29 '17 at 21:19
• A LinkedHashSet will remove duplicates and keep results in order – mcgyver5 Jun 29 '17 at 21:47

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)) {
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 Jun 29 '17 at 23:56
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());

• 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. – Tamoghna Chowdhury Jul 2 '17 at 6:06