Count the number of duplicated chars in a string

Question

It's an exercise, which I found on Codewars.

Instructions:

Write a function which returns the count of distinct case-insensitive alphabetic characters and numeric digits which occur more then once in a given string. The given string can be assumed to contain only alphabets (lower-, uppercase) and numerics.

Examples:

• "abcde" results in 0, because no characters repeats more than once.

• "aabbcde" results in 2, because of 'a' and 'b'.

• "aabBcde" => 2, because 'a' occurs twice and 'b' occurs twice (b and B).

• "indivisibility" => 1, because 'i' occurs six times.

• "Indivisibilities" => 2, because 'i' seven times & 's' twice.

• "aA11" => 2, because 'a' and '1'.

• "ABBA" -> 2, because 'A' and 'B' each twice.

My (valid*) solution:

fun duplicateCount(text: String): Int {
 var count = 0
 var invalid = ArrayList<Char>()
 var i = 0
 while (i < text.length) {
 if (invalid.contains(text[i].toLowerCase())) {
 i++
 continue
 }
 var j = i + 1
 while (j < text.length) {
 if (text[i].toLowerCase() == text[j].toLowerCase()) {
 invalid.add(text[i].toLowerCase())
 count++
 break
 }
 j++
 }
 i++
 }
 return count
}

*It has passed the unit-tests.

What are your thoughts about my implementation?

How could it be improved? What would you have done differently and why?

Looking forward to reading your comments and answers.

• Gábor: Use a HashSet, add every incoming character to the set but before you do, increment a counter if it's already there. No need to loop the string many times, just once.
• tieskedh: @Gábor yup, that's roughly my answer.

Answer 1

Some little things. The count is already counted by ArrayList(), with the for() loop you can't miss/forget a i++ and with the c there is no need for another toLowerCase().

fun duplicateCount(text: String): Int {
 var invalid = ArrayList<Char>()
 for (i in 0 until text.length) {
 var c = text[i].toLowerCase()
 if (invalid.contains(c))
 continue
 for (j in i+1 until text.length) {
 if (c == text[j].toLowerCase()) {
 invalid.add(c)
 break
 }
 }
 }
 return invalid.size;
} 

• RoToRa: I think you are confusing your languages. Those aren't valid Kotlin for loops and size isn't a method.
• Simon Forsberg: The for-loop can be easily fixed by using for (i in 0 until text.size)
• Simon Forsberg: And instead of calling ArrayList constructor, use var invalid = mutableListOf<Char>(). And it should be a Set instead, so mutableSetOf would be even better.
• tieskedh: @Holger, ArrayList is only available on Kotlin-Java and Kotlin-js, while mutableListOf is available in common-Kotlin (every Kotlin version). Also, you don't change the reference of your variables. Therefor, you should use val instead of var. Also, you could use c in invalid instead of invalid.contains(c)

Answer 2

A more straight forward solution would be to count each character and then to count the characters that have a count larger than 1. This can easily be done using the functional methods available in Kotlin's standard library:

fun duplicateCount(text: String): Int =
 text.toLowerCase()
 .groupingBy { it }.eachCount()
 .count { it.value > 1 }

.groupingBy { it }.eachCount() creates a map (Map<Char, Int>) that assigns each character in the string to its count.

.count { it.value > 1 } then counts all entries in the map where the count is more than one.

---

EDIT: Inspired by @SimonForsberg here in comparision a procedural implementation of the same algorithm. I also modified the version above to use the better count(predicate) method, which I originally forgot about.

fun duplicateCount(text: String): Int {
 val lcText = text.toLowerCase()
 val characterCount = mutableMapOf<Char, Int>()
 for (i in 0 until lcText.length) {
 val char = lcText[i]
 characterCount.put(char, 1 + characterCount.getOrDefault(char, 0))
 }
 var count = 0
 for (entry in characterCount) {
 if (entry.value > 1) {
 count++
 }
 }
 return count
}

• Simon Forsberg: While it's true that Kotlin's standard library provides a bunch of methods for this, I assume that the code is written as a learning exercise and probably avoids these on purpose.
• RoToRa: @SimonForsberg I do agree, but its sometimes difficult to say what exactly should be avoided. I considered also showing my algorithm in a procedural style, but I thought is was also worth showing a more Kotlin-like style

Answer 3

1. lowerCase and uppercase should be treated te same? Let's make them the same:

   val lowerText = text.toLowerCase()
   

2. Check for duplicates? A set doesn't allow duplicates.
   Also, add returns a Boolean which tells if the value is added.
   This means we can get a list off all the unique values by checking if we can add it to a set:

   fun duplicateCount(text: String): Int {
    val lowerText = text.toLowerCase()
    val invalid = mutableSetOf<Char>()
    val chars = lowerText.filter{ invalid.add(it) }
    return chars.length
   }
   

3. But we needed the duplicates...
   Well, this means that we need to get the items that already were in our set.
   As we can only add items to our set once, the duplicates are the items where we cannot add it (because they are already added):

   fun duplicateCount(text: String): Int {
    val lowerText = text.toLowerCase()
    val invalid = mutableSetOf<Char>()
    val chars = lowerText.filterNot{ invalid.add(it) }
    return chars.length
   }
   

4. What happens if we come come across a character three times:

   1. it can be added -> add returns true -> we ignore it
   2. it can't be added -> add returns false -> we add it to chars.
   3. it can't be added -> add returns false -> we add it to chars again.

   but, I guess we can change the list into a collections that doesn't allow duplicates :-)

   fun duplicateCount(text: String): Int {
    val lowerText = text.toLowerCase()
    val invalid = mutableSetOf<Char>()
    val chars = lowerText
    .filterNot{ invalid.add(it) }
    .toSet()
    return chars.length
   }
   

or without redundant params:

 fun duplicateCount(text: String): Int {
 val invalid = mutableSetOf<Char>()
 return text
 .toLowerCase()
 .filterNot{ invalid.add(it) }
 .toSet()
 .length
 }

5*. We can optimize it a bit by adding it immediately to a Set.
We can do this by calling filterNotTo instead of filterNot.
We need to get the filterNotTo for classes with an iterator (which implements Iterable), but String doesn't have this.
Fortunately, String has a function asIterable which returns an Iterable for the String.

When we combine this we get:

fun duplicateCount(text: String): Int {
 val invalid = mutableSetOf<Char>()
 return text
 .toLowerCase()
 .asIterable()
 .filterNotTo(mutableSetOf()){
 invalid.add(it.toLowerCase())
 }.size
}