0
\$\begingroup\$

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

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?

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for you input I have learned something new and just improved my code. \$\endgroup\$ – TheLearner Jun 29 '17 at 23:56
1
\$\begingroup\$
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());
| improve this answer | |
\$\endgroup\$
  • \$\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 Jul 2 '17 at 6:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.