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.

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;
} 

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
}

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
}