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.

Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.