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\$
8
  • \$\begingroup\$ I think this is just O(n) because it only has one for loop. \$\endgroup\$ Commented Jul 11, 2016 at 0:56
  • \$\begingroup\$ @Sometowngeek thank you! The for loop = n, and then the if statement = n, so 2n = O(n)? \$\endgroup\$
    – jellyxbean
    Commented Jul 11, 2016 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\$ Commented Jul 11, 2016 at 1:13
  • \$\begingroup\$ Interview Cake has a good explanation of Big-O Notation. \$\endgroup\$ Commented Jul 11, 2016 at 1:15
  • \$\begingroup\$ @Sometowngeek great, thanks very much for responding. Will check Interview Cake out! \$\endgroup\$
    – jellyxbean
    Commented Jul 11, 2016 at 1:16

2 Answers 2

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
  • 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\$ Commented Jul 11, 2016 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\$
2
  • \$\begingroup\$ Nice spot. Most people forget that char could be either signed or unsigned. \$\endgroup\$ Commented Jul 11, 2016 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
    Commented Jul 11, 2016 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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