1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I think this is just O(n) because it only has one for loop. \$\endgroup\$ – Sometowngeek Jul 11 '16 at 0:56
  • \$\begingroup\$ @Sometowngeek thank you! The for loop = n, and then the if statement = n, so 2n = O(n)? \$\endgroup\$ – jellyxbean Jul 11 '16 at 1:12
  • 3
    \$\begingroup\$ With the Big-O notation, the coefficients are ignored. So if it has three separate for loops, and an if statement, it's still O(n), not O(4n). \$\endgroup\$ – Sometowngeek Jul 11 '16 at 1:13
  • \$\begingroup\$ Interview Cake has a good explanation of Big-O Notation. \$\endgroup\$ – Sometowngeek Jul 11 '16 at 1:15
  • \$\begingroup\$ @Sometowngeek great, thanks very much for responding. Will check Interview Cake out! \$\endgroup\$ – jellyxbean Jul 11 '16 at 1:16
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Expressing your system as Most programmers is wrong. Yes that style is popular but "most" is a stretch (especially in C++). Express the different styles available and name them. \$\endgroup\$ – Martin York Jul 11 '16 at 17:37
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice spot. Most people forget that char could be either signed or unsigned. \$\endgroup\$ – Martin York Jul 11 '16 at 17:40
  • 1
    \$\begingroup\$ as an aside, note he says 'assuming ASCII' . That doesnt have chars >127. He should still verify tho. \$\endgroup\$ – pm100 Jul 11 '16 at 18:04

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.