isUnique? Determine if a string has all unique characters

Implement an algorithm to determine if a string has all unique characters.

First attempt

procedure isUnique(str) 
1. arr = array of all string characters
2. sorted = array.sort()
3. for i=0 to str.length
   A. if sorted[i] == sorted[i+1] 
      A1. return false
4. return true

JavaScript Implementation

The upper bound of this algorithm is the filter function, which its runtime complexity is 0(n).

The other constants, split() and sort() runtime complexities are 0(n) and 0(n log n) respectively.

Better one

Most programming languages have a Set data type, sets cannot contain duplicate elements, which means we can do the following:

procedure isUnique(str)
1. return new Set(str).size == str.length

Much cleaner, isn’t it?

JavaScript Implementation

Using regular expression

Both solutions above converted the string into other data structures to check whether it has all unique characters or not. What if you cannot use additional data structures? Then I’ll use RegExp:


Leave a comment

Your email address will not be published.