[CTCI: Arrays and Strings] 1. Is Unique

This is the first post for the CTCI. I will post the solution to the CTCI problem regularly. This series will give you intuition and strategy, how to come up with the solution problem.

1. Is Unique: Implement an algorithm to determine if all characters in a string are unique. What if you cannot use additional data structures?

You need to be able to come up with keywords: ASCII, Unicode, the number of characters, flag

We need to thread those beads into one algorithm. First of all, it is important to assume which character type we are going to use, ASCII or Unicode, it is important because of memory. ASCII characters are8 bits, and Unicode characters are normally 16 bits. We choose the ASCII code, and then how many characters should we consider. We only consider 128 characters in ASCII. Therefore, we conclude the first condition:

1. If the String exceeds the number of unique characters, 128 in our cases, we should return false.

Then, we still have repeated characters in the string, its length is less than 128. How do we find this? We can use a flag. The flag needs to indicate repetition. We can use two types of flag, a boolean array, and a bit vector.

2. Flag can indicate the character was in the string already.

Code: