4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ The code doesn't work because you used end of line comments and had a formatter add newlines to them. \$\endgroup\$ – TorbenPutkonen Jan 8 at 15:26
  • \$\begingroup\$ Before we go into fixing the code, tell us are you restricted to ASCII or are you expected to be able to deal with the full Unicode character set? \$\endgroup\$ – TorbenPutkonen Jan 8 at 15:31
  • \$\begingroup\$ @TorbenPutkonen My apologies for the incorrect formatting. I have edited the code. I believe that the problem is restricted to ASCII, not Unicode. I have included a link to the problem also. \$\endgroup\$ – David Jan 8 at 17:17
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Let me know if you think something is wrong in the answer. 😀 \$\endgroup\$ – bhathiya-perera Jan 8 at 17:58
  • \$\begingroup\$ Thank you for the detailed comment. I will try to re-implement the solution using HashMap. I have yet to learn the Map and Collection API. Solving these problems with Java makes me appreciate the simple syntax of Python. \$\endgroup\$ – David Jan 8 at 19:11
  • \$\begingroup\$ @bhathiya-perea, I do have one question. What would the time complexity be for the solution using HashMap? Would it be O(n) ? \$\endgroup\$ – David Jan 8 at 19:14
  • 1
    \$\begingroup\$ @David ah yes it would be armotized O(n) \$\endgroup\$ – bhathiya-perera Jan 8 at 19:22
  • 1
    \$\begingroup\$ @TorbenPutkonen IMHO this is ASCII only as it is a programming challenge, these tests usually checks if user can build a fast algorithm for the given scenario. But in real world pretty much everything is Unicode. If someone asked this as an interview question then the I would ask is this for ASCII only? And they would most probably say "Yes". \$\endgroup\$ – bhathiya-perera Jan 10 at 11:53
4
\$\begingroup\$

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(); 
} 
\$\endgroup\$
  • \$\begingroup\$ Thank you for your input. I am still learning the ins and outs of Java and it's data structures. \$\endgroup\$ – David Jan 13 at 15:51

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.