I'm practicing algorithms (for future interviews) while learning about Big O notation and was wondering if there's a faster or more optimal way of writing an algorithm to see if a string has all unique characters (assuming you can't use additional data structures).- (BOOL)containsUniqueCharacters:(NSString *)string {    //Make sure that it's case insensitve    string = [string uppercaseString];    //Create a buffer for our string    NSUInteger length = [string length];    unichar buffer[length];    [string getCharacters:buffer range:NSMakeRange(0, length)];    //Iterate through each of our characters    for (int i = 0; i < length; i++) {        //Iterate through every other character and compare it with our current character        for (int n = 0; n < length; n++) {            //Compare current character with every other character            if (buffer[i] == buffer[n] && i != n) {                return NO;            }        }    }    return YES;}If I'm correct, is the time complexity for this \$O(n^2)\$, and the space complexity \$O(1)\$?
Determine if a string has all unique characters
algorithm;strings;objective c;ios
You are right on the time complexity, but wrong on the space complexity.because you copy the data from the String to the buffer, you incur an \$O(n)\$ space complexity too.vnp has suggested an alternate algorithm that scales at better than \$O(n^2)\$, but you can also significantly improve your current algorithm. Your current system compares each character with every other character twice.... Consider the word and, you will compare a with n and d, then compare n with a and d, but you have already done the n and a comparison.What you need to do is alter your inner loop to restrict the range of the comparison. Consider the following://Iterate through each of our characters// **Note, start from 1for (int i = 1; i < string.length; i++) {    unichar letter = [string characterAtIndex:i];    //Iterate through all previous other characters and compare it with our current character    for (int n = 0; n < i; n++) {        //Compare current character with every other character        if (letter == [string characterAtIndex:n]) {            return NO;        }    }}The above code still checks each letter, but only does it once. It is smart about the indices, so you only compare previous letters with the current, and it does half the comparisons. Also, by using a starting offset of 1, and a < comparison on the n loop, you never compare the character against itself.For smallish strings (less than 100 characters or so), this \$O(n^2)\$ algorithm, using no additional space (other than the letter variable), will be very fast still.