5
\$\begingroup\$

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)\$?

\$\endgroup\$
5
\$\begingroup\$

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 1
for (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.

\$\endgroup\$
  • \$\begingroup\$ Wow this is awesome. Thank you. I love the fact that you explain how using the < comparison prevents the loop from comparing the character against itself, that's something I had to overcome originally using a second condition in my if statement. Your entire answer is extremely helpful, thank you. \$\endgroup\$ – KingPolygon Sep 22 '14 at 22:36
  • 2
    \$\begingroup\$ Plural of index is indices. Sorry it just gives me shivers. \$\endgroup\$ – vnp Sep 22 '14 at 22:43
  • \$\begingroup\$ @vnp - absolutely right, except when talking about database indexes, it is common to use that plural... and I come from a DB background, and it shows... ;p \$\endgroup\$ – rolfl Sep 22 '14 at 22:47
6
\$\begingroup\$

I would suggest an algorithmically better O(n) solution by using a buffer or hashtable or other such structure to record whether or not you have "seen" a character.

For example if you are dealing with a basic string containing char, then you can get away with a bitset of size 256. Each character you see marks a bit. If the bit was already marked, return YES.

Furthermore, if the size of the string you're testing is longer than 256, then that is an automatic NO (not all unique chars) as well.

Since you are dealing with unicode for which the possible values a character can take are very many, then you will want to use a hash table. It will be dramatically faster than even any O(n log n) sorting method.

\$\endgroup\$
  • \$\begingroup\$ +1 for the suggestion of the automatic longer-than-256 string, but the assumption for this program was "(assuming you can't use additional data structures)." which makes the hash table out-of-scope. Without that restriction it would be a great suggestion. \$\endgroup\$ – rolfl Sep 22 '14 at 23:43
  • \$\begingroup\$ That's an absurd restriction. Well, a bit set that is as large as the set of unicode codepoints is impractical as it would likely be much larger than even the entire string being processed. But technically speaking, it is still a constant factor. Which means O(1) space. I'm all for big-O notation, don't get me wrong... \$\endgroup\$ – Steven Lu Sep 23 '14 at 2:16
  • \$\begingroup\$ I believe that 4 bytes are enough to store all existing unicode characters. Am I wrong? \$\endgroup\$ – Emanuele Paolini Sep 24 '14 at 5:09
  • \$\begingroup\$ Well, that's how much space a single character takes. We gotta have a bit set for each possible character. Actually Unicode comprises 1,114,112 code points (cf. <127 for ASCII and 255 for 8-bit chars), so this would really only take up just over 100KB worth of bit set space. This is actually very manageable, can probably even fit on the stack (don't do that, use std::bitset, which will place storage on heap). It should also outperform the hash table as well. The trick now is mainly in properly parsing and decoding the unicode chars to map into such a bit set buffer. \$\endgroup\$ – Steven Lu Sep 24 '14 at 9:56
3
\$\begingroup\$

Your analysis is correct. Sorting an original string, followed by a linear scan to fund duplicates, reduces the time complexity to \$O(n \log n))\$, for a price of \$O(\log n)\$ space. If the string modification is not allowed, an additional \$O(n)\$ space penalty is incurred.

\$\endgroup\$
  • 1
    \$\begingroup\$ Space is still O(n) \$\endgroup\$ – Steven Lu Sep 22 '14 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.