Checking if a string has all unique characters

Question

I'm wondering if this code can be optimized in terms of time complexity. The problem is checking to see if a string has all unique characters.

#include <iostream>
#include <string>
using namespace std;

//Assuming ASCII 

bool checkString (string user) {
    if (user.length() > 256) 
    {
        return false;
    }

    //creating a boolean array of size 256
    //setting all values to false (0)
    bool check[256] = {false};   

    for (int i = 0; i < user.length(); i++)
        {
        int value = user.at(i); 
            if (check[value] == true)
            {
                return false; 
            }

            else 
            {
                check[value] = true;
            }
        }
    return true;
}


int main() {

    string user;
    cout << "Please enter in a string: ";
    cin  >> user;

    cout << checkString(user) << endl;

    return 0;
}

I'm not very good with determining the time complexity. Right now, would it be \$O(n^2)\$ (because of the for loop)?

Answer 1

Looks good to me from a big-O point of view.

C++wise, you have some misconceptions:

//setting all values to false (0)
bool check[256] = {false};

This explicitly initializes only the first element to false; the remaining 255 elements are value-initialized, which in layman's terms means zero-initialized, which means yes they're initialized to false as well in this case; but your comment is misleading, in that

bool uncheck[256] = {true};

would not initialize all 256 elements to true — it would explicitly initialize the first element to true and then value-initialize the other 255 elements (to false).

---

for (int i = 0; i < user.length(); i++)
    {
    int value = user.at(i); 
        if (check[value] == true)
        {
            return false;

This indentation is all screwed up. You should indent whenever you enter a new scope, and dedent when leaving a scope. So for example it would be sensible to write

for (int i = 0; i < user.length(); i++)
{
    int value = user.at(i); 
    if (check[value] == true)
    {
        return false;

but actually most programmers would just write

for (int i = 0; i < user.length(); ++i) {
    int value = user[i]; 
    if (check[value]) {
        return false;

(notice the cuddled braces, the removal of the explicit test-for-equality with true, the default preference for ++i over i++, and the preference for fast operator[] over slow .at() when the index is statically known to be in-bounds).

---

bool checkString (string user)

This function signature tells the function to take the parameter user by value, which means "make a copy." Since you don't need a copy for any reason, you should by default prefer to take a reference:

bool checkString(const string& user)

(and notice the removal of the extra space in between the function name and its parameter list; we don't write f (x) in C++ for the same reason you don't write “f  (x)” in math class).

---

It might be an interesting research project for you to figure out what you'd have to change to make // Assuming ASCII no longer required.

Answer 2

This extract:

    int value = user.at(i); 
    if (check[value] == true)

has a serious problem - if the character at i is negative, you'll index off the beginning of the array. (Remember, it's implementation-defined whether plain char is a signed or unsigned type).

It's more idiomatic (and slightly safer) to use a range-based for loop:

for (auto c: user) {
     auto& f = check[reinterpret_cast<unsigned_char>(c)];
     if (f) return false;
     f = true;
}

(The extra safety is because you no longer need to ensure that you're counting the same container as you're indexing - which can be an issue in bigger functions).

Also, prefer to avoid using namespace, particularly at global scope. You might choose to have it inside your throwaway main, but is it really that hard to write std:: once in your function signature? It can save you from unpleasant surprises.

Other issues already addressed in existing answers, so I won't mention them here.