Counting Duplicates - Code War

Question

This is a problem from CodeWar.

Write a function that will return the count of distinct case-insensitive alphabetic characters and numeric digits that occur more than once in the input string. The input string can be assumed to contain only alphabets (both uppercase and lowercase) and numeric digits.

EX: "abba" -> 2, "aabBcde" -> 2.

Here is my solution in Java:

public class CountingDuplicates {
      public static int duplicateCount(String text) {
      String textLower = text.toLowerCase(); 
      char[] charArray = textLower.toCharArray(); 
      String uniqueRepeats = ""; //Will keep track of unique repeats. 
      int count = 0;

      for(int i = 0; i < charArray.length - 1; i ++) { 
      String restOfString = textLower.substring(i + 1); 

      //Convert single char to String to be used in method.
      String character = Character.toString(charArray[i]); 

      //If not in uniqueRepeats, check if it is a repeat. 
      if(!uniqueRepeats.contains(character)) {
          if(restOfString.indexOf(character) != -1) { 
     //If it is a repeat, increase count and concat it to uniqueRepeats
              count++;
              uniqueRepeats += character;
     }
    }
   }
  return count; 
  } 
}

Some improvements that I can think of is using a HashMap to store the repeats so that I do not have to create a new string object for every repeat If you guys have any suggestions on code readability, code structure, or better implementation for this problem, please leave me a comment. Thank you! EDIT - Here is the link to the problem: https://www.codewars.com/kata/counting-duplicates/train/java

Answer 1

Let's see what is the Big O of your code.

1. In new versions of Java substring creates a new String and performs in \$O(n)\$ (In older versions this is \$O(1)\$)
2. uniqueRepeats.contains(character) results in \$O(m)\$ where \$m\$ is count of unique characters.
3. restOfString.indexOf(character) != -1 - this is again \$O(n)\$
4. uniqueRepeats += character Depending on the JVM this might end up creating set of StringBuilder objects or set of String objects that are discarded. So this is probably \$O(m^2)\$
5. You are doing this for \$n\$ characters.

So time complexity is - \$O(n *(n + m + m^2))\$ in some situations \$m\$ can be as large as \$n\$. So if we simplyfy things we get \$O(n^3)\$.

Ideas:

• This is where your HashMap idea would've been better. We can simply store Char and an Integer count. Then iterate over your map to count all elements that has more than \$1\$ element. LinkedHashMap is very useful for a situation like this.
• Why is LinkedHashMap better? Because it has an internal linked list that allows faster iteration.
• We can also use an array if this is ASCII only. (But it is easier with a Map).
• This will result in armotized \$O(n)\$. Which is lot better.
• Either way all these are theoretical and it is always better to profile things.

---

Code

//Will keep track of unique repeats.
//Convert single char to String to be used in method.
//If not in uniqueRepeats, check if it is a repeat. 
//If it is a repeat, increase count and concat it to uniqueRepeats

• You have mentioned what you are doing in comments. We can also understand that from code itself. So it is better to include why comments.
• I recommend that you use an IDE to indent code. Code is clearly not indented accurately.

if(!uniqueRepeats.contains(character)) {
    if(restOfString.indexOf(character) != -1) {

• Be consistent. We can use contains to both above statements.

_References

• https://stackoverflow.com/a/1532483/1355145
• http://java-performance.info/changes-to-string-java-1-7-0_06/
• https://stackoverflow.com/questions/26311776/why-iteration-through-buckets-in-linkedhashmap-is-faster-than-hashmap

Answer 2

Like bhathiya-perera and yourself suggested this can be better implemented using a HashMap and simply count the characters.

However in my opinion your attempt isn't that bad. The problem is you are using the wrong methods and data structures and you are coping/creating strings too much.

First you don't need to create charArray which is an unnecessary copy of the string. You are only using for the length (with is identical to the length of the original string) and to get the character, which can be done with the .charAt() method of String.

String is the wrong data structure for uniqueRepeats. The only thing you do with that is check if it contains a specific character. The optimized data structure for that would be a HashSet<Character>:

Set<Character> uniqueRepeats = new HashSet<>();

Counting the duplicates yourself with count is also not necessary. You can just take the size() of uniqueRepeats at the end.

Creating restOfString is also not necessary, since String has a variant of indexOf that searches from a given index instead of from the start.

textLower.indexOf(character, i + 1) != -1

When getting the character from the string, you don't need to convert it into a String. Generally anything that can be done with a String, usually can be done with a character:

char character = textLower.charAt(i); 

Finally the two nested ifs can be combined into one using &&.

Final code:

public static int duplicateCount(String text) {
  String textLower = text.toLowerCase(); 
  Set<Character> uniqueRepeats = new HashSet<>();

  for (int i = 0; i < textLower.length - 1; i ++) { 
    char character = textLower.charAt(i);

    if (!uniqueRepeats.contains(character) && textLower.indexOf(character, i + 1) != -1) { 
       uniqueRepeats.add(character);
    }
  }

  return uniqueRepeats.size(); 
}