Implement O(n) algorithm for determining if a string has all unique characters?

Question

Here I have O(n^2) algorithm implemented in C++ function to determine if a string have all unique characters.

bool IsUnique2(char *str)
{
    char instr[256];
    strcpy(instr,str);
    bool repeat = false;
    int i;
    for(i = 0; i<strlen(instr); i++)
    {
        int j;
        for(j=i+1; j<strlen(instr); j++)
        {
            if(instr[i]==instr[j])
            {repeat = true; break;}
        }
        if(repeat) break;
    }

    return !repeat;
}

This algorithm checks every char of the string with other char of the string in order to find if they are repeated. This approach have time complexity of O(n^2) with no space complexity. Can someone suggest an algorithm implementation of time complexity O(n) ?

Answer 1

You could keep an unordered_set<char> of characters that you've already seen, and bail out if the character you're at is already in the set. Because access to the set is amortized constant time, your algorithm will run in O(n).

Instead of a set, you could also use an array of bool, because a char typically has a very small range (0-255).