CODEWITHSUNDEEP
algorithmkotlinbig-o
M.Lucas
M.Lucas

Reputation: 29

Complexity of a method checking whether all characters in the string are unique

I am trying to write a function in kotlin that checks if all characters in the string are unique.

fun isUnique(s: String): Boolean {
     return s.filter {
          char -> s.count(char) == 1
     } == s
}

I would like to know what is the runtime complexity of this method. Is it O(n) or O(n pow2) (because we touch each char twice in the filter function and in the count function)? Also is the space complexity O(1)?

Alternatively, I wrote this method

fun isUnique2(s: String): Boolean {
    return s.groupBy {
        char -> s.count(char)
    }.filterKeys{key > 1}.isEmpty()
}

what are the space and time complexity of this method?

I appreciate any help

Thank you

Upvotes: 1

Views: 540

Answers (2)

Joffrey
Joffrey

Reputation: 37799

The first implementation is O(n^2), not simply because you touch each char twice (it's actually 4 times because of ==, but could be just twice if you compared sizes instead), but because for each char you consider in the filter, you iterate the whole N characters of the string via count().

It's not the same to iterate the string twice, and to iterate the string once per char of the string. This is the difference between O(2n) (= O(n)) and O(n^2).

This first implementation also allocates an extra collection with filtered elements, which in the worst case contains all chars, so O(n) space.

The second implementation does even more work, you still start with an O(n^2) step because you count through the whole string to build each group. But then you add more space complexity because you allocate more intermediate collections.

You can have an O(n) solution, with O(n) space by simply turning your string into a Set and comparing sizes:

fun isUnique(s: String): Boolean {
     return s.toSet().size == s.length
}

Internally, toSet() uses a LinkedHashSet, for which insertion has an amortized cost of O(1). This means the string is iterated only once, and each char is inserted in O(1) into the set, which ensures at insertion time that there are no duplicates. Comparing sizes is also O(1) in general because most collections have a constant-cost way to access their size.

Upvotes: 1

Михаил Нафталь
Михаил Нафталь

Reputation: 7902

Both implementations have O(n^2) time complexity and O(n) space complexity.

With the following solution you can have O(n) time complexity (keeping O(n) space) in the worst case:

fun isUnique(s: String): Boolean {
    val hashset = hashSetOf<Char>()
    return s.all { hashset.add(it)  }
}

But generally this algorithm may end up (returning false) before reaching end of the string (if we met some repeating char, no need to check remaining chars), so in the best case it may end on the 2-nd iteration.

The magic behind this consists of two parts:

  1. add method of Set returns false if this set already contained the specified element
  2. all method returns false on the first predicate, which evaluated to false

Upvotes: 2

Related Questions