# 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) {
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("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.

What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? This year, I’m writing Busy Beavers, a unique interactive book on computability theory. You and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

It’s only \$19, and you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

After months of secret toil, I and Andrew Carr released Everyday Data Science, a unique interactive online course! You’ll make the perfect glass of lemonade using Thompson sampling. You’ll lose weight with differential equations. And you might just qualify for the Olympics with a bit of statistics!

It’s \$29, but you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

### More by Jim

Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer.