Implement an algorithm to determine if a string has all unique characters without using any additional data structures?
Time complexity is O(n), where n is the length of the string, and space complexity is O(n).
Using Bit Vector:
We can reduce our space usage a little bit by using a bit vector. We will assume, in the below code, that the string is only lower case ‘a’ through ‘z’. This will allow us to use just a single int.
Imagine that you have an array of 26(=ASCII value of Character-‘a’) Booleans, each one tracking whether a particular character has appeared in the string already. You start with all of them false (=0).
Now iterate all the characters of the string and each time you see a character you look into the array slot for that character.
If it's , this is the first time you've seen the character and you can set the slot to .
If it's , you've already seen this character and you can immediately report that there's a duplicate.
We have been opted a clever trick to mark the appearance of the character. Since there are only 26 different characters possible and there are 32 bits in an , the solution creates an variable where each bit of the variable corresponds to one of the characters in the string.
Instead of reading and writing an array, the solution reads and writes the bits of the number.
For example, look at this line:
int bitPos = 1 << val;
What does checker & bitPos do?
Well, creates an value that has all bits zero except for the th bit. It then uses bitwise AND to AND this value with checker. If the bit at position in checker is already set, then this evaluates to a nonzero value (meaning we've already seen the number) and we can return false. Otherwise, it evaluates to 0, and we haven't seen the number.
The next line is this:
This uses the "bitwise OR with assignment" operator, which is equivalent to
This ORs checker with a value that has a set only at position , which turns the bit on. It's equivalent to setting the th bit of the number to 1.