CODEWITHSUNDEEP
kotlinfunctional-programmingunique
h1h1
h1h1

Reputation: 780

Kotlin - Unique Characters in String

My function should return a boolean indicating whether the input String contains all unique characters.

e.g. "abc" returns true, "abca" returns false

fun uniqueCharacters(s: String): Boolean = s.groupBy { it }
    .values
    .stream()
    .allMatch { it.size == 1 }

Is there a more efficient way of solving this problem? If I was solving this in non-functional way I would store all the characters in a Map with the value being the count of that character so far, if it is greater than one then break and return false.

Not sure how best to translate this into a functional Kotlin piece of code.

Upvotes: 2

Views: 4485

Answers (3)

Fatih Santalu
Fatih Santalu

Reputation: 4701

Yet another approach

fun String.uniqueCharacters(): Boolean = this.toCharArray().distinct().isNotEmpty()

Upvotes: 2

IR42
IR42

Reputation: 9672

You can use all function and Set::add as predicate for it

fun main() {
    println("abc".allUnique()) // true
    println("abca".allUnique()) // false
}

fun String.allUnique(): Boolean = all(hashSetOf<Char>()::add)

It's lazy, the function returns the result when it finds the first duplicate

Upvotes: 12

gidds
gidds

Reputation: 18537

Perhaps the simplest way is to create a Set of the characters, and check its size:

fun String.isUniqueCharacters() = toSet().size == length

(Since this function depends only on the contents of the string, it seems logical to make it an extension function; that makes it easier to call, too.)

As for performance, it's effectively creating a hash table of the characters, and then checking number of entries, which is the number of unique characters.  So that's not trivial.  But I can't think of a way which is significantly better.

Other approaches might include:

  • Copying the characters to an array, sorting it in-place, and then scanning it comparing adjacent elements.  That would save some memory allocation, but needs more processing.

  • As above, but using a hand-coded sort algorithm that spots duplicates and returns early. That would reduce the processing in cases where there are duplicates, but at the cost of much more coding.  (And the hand-coded sort would probably be slower than a library sort when there aren't duplicates.)

  • Creating an array of 65536 booleans (one for every possible Char value*), all initialised to false, and then scanning through each character in the string checking the corresponding array value (returning false if it was already set, else setting it).  That would probably be the fastest approach, but takes a lot of memory.  (And the cost of initialising the array could be significant.)

As always, it comes down to trading off memory, processing, and coding effort.

(* There are of course many more characters than this in Unicode, but Kotlin uses UTF-16 internally, so 65536 is all we need.)

Upvotes: 5

Related Questions