Determine if a string has all unique characters

Question 1.1 of Cracking the Coding Interview:

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Here’s a recursive solution. If the string is empty, all characters are unique. Otherwise, split the string into head and tail; if head does not occur in tail, and all characters in tail are unique, then the full string is unique.

Here’s a solution in C:

#include <stdbool.h>
#include <assert.h>

bool has_all_unique_characters(char* s) {
  char head = s[0];
  if (head == '\0') {
    return true;
  } else {
    for (int i = 1; s[i] != '\0'; i++) {
      if (s[i] == head) return false;
    }
    return has_all_unique_characters(s+1);
  }
}

int main(int argc, char** argv) {
  assert(!has_all_unique_characters("hello"));
  assert(!has_all_unique_characters("abracadabra"));
  assert( has_all_unique_characters("world"));
  assert( has_all_unique_characters(""));
  return 0;
}

CTCI argues that this algorithm is O(n^2) where n is the length of the string. I disagree and claim it’s O(n), because there are only 255 possible bytes. The worst-case input is something like [1,2,3,...,253,254,255,255,255,...,255], which causes 254 full iterations over the full string. This can be brought down to O(1) with an initial check: if the string is longer than 255 bytes, there must be a duplicated character, by the pigeonhole principle.

This page copyright James Fisher 2020. Content is not associated with my employer. Found an error? Edit this page.

Jim Fisher

CV

Speaking

Blogroll

RSS

TigYog

Kickabout