12
\$\begingroup\$

Following is my code to check if string has unique chars.

I am assuming string would have only ascii chars.

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

int main()
{
    array<char,255> arr;

    char *str = "ABCADEFGHIJKL";

    for (int i = 0; i < 255; i++)
        arr[i] = 0;

    int i = 0;

    while (str[i])
    {
        if (arr[str[i]] == 1)
        {
            cout << "Not unique";
            return 0;
        }

        arr[str[i]] = 1;

        i++;
    }

    cout << "Unique";

    return 0;
}
\$\endgroup\$
16
\$\begingroup\$
char *str = "ABCADEFGHIJKL";

This should be const char* str because string literals are usually stored in read-only memory.

for (int i = 0; i < 255; i++)
    arr[i] = 0;

You can get rid of this loop by using aggregrate initialization:

array<char,255> arr{};  // zero-initialize all elements
int i = 0;

while (str[i])

You can get rid of the index variable i by using the string pointer for iteration. Also use a for loop which is more concise:

for(; *str; ++str)
{
    if (arr[*str] == 1)
    {
        cout << "Not unique";
        return 0;
    }

    arr[*str] = 1;
}

I would also change array<char,255> to array<bool,255> which expresses intend better as you only use values of 0 and 1 anyway.

Edit:

As pointed out in this answer the OPs code (and mine aswell) is vulnerable to buffer overruns. Although OP stated that input will be ASCII only (which is in the range of 0..127), if the string is user input then it shouldn't be trusted.

One way the vulnerability could be mitigated would be a range check of the input characters. If they are out of the ASCII range, discard them, replace them by a "dummy" value or do whatever fits your situation.

\$\endgroup\$
  • \$\begingroup\$ Agree with all your points. One question, why to use const for char * as literal is already const. \$\endgroup\$ – Pranit Kothari Jun 11 '17 at 14:54
  • 5
    \$\begingroup\$ @PranitKothari The literal yes, but not str. If you did something like str[2] = 'a';, you would have undefined behaviour. If str is const char*, however, your compiler will complain at compile time. \$\endgroup\$ – Ben Steffan Jun 11 '17 at 14:56
  • 1
    \$\begingroup\$ @PranitKothari if you compile with more warnings -Werror -Wextra -wpedantic as you should you will find it is in error to try to store a literal string (of type const char*) into a variable of type char* \$\endgroup\$ – cat Jun 11 '17 at 23:31
13
\$\begingroup\$

There are two independent possibilities for a buffer overflow in your code.

  1. An array<char,255> arr; will provide indices 0..254 (with 255 pieces). If str is engineered to contain a 255 byte, the code is guaranteed to access (and maybe even write to) memory which does not belong to you... anything can happen that way.

  2. The code will only work assuming the default char is unsigned. That might or might not be the case: The standard does not specify if plain char is signed or unsigned. If you read/write with negative indices, even more spectacular things can happen.

\$\endgroup\$
  • \$\begingroup\$ I just wanted to add those blatant omissions from the reviews when I saw this. Nice one! \$\endgroup\$ – Deduplicator Jun 11 '17 at 18:00
  • \$\begingroup\$ He explicitly stated that input will only be ASCII, so there wouldn't be values outside of range (strict ASCII is only 0..127). Anyway you are right that user input should not be trusted. \$\endgroup\$ – zett42 Jun 11 '17 at 21:28
  • \$\begingroup\$ Thanks for clarifying, when I was making array of 255 I was confused between 255 and 256. For second point, is there any possibility, ASCII chars could be singed? \$\endgroup\$ – Pranit Kothari Jun 12 '17 at 3:21
  • \$\begingroup\$ @PranitKothari Pure ASCII character set is in range of 0..127, so it can't be negative. Everything greater than 127 would result in a negative value when converted to signed char. But when there is user input, negative char values can and will happen. \$\endgroup\$ – zett42 Jun 12 '17 at 6:31
  • \$\begingroup\$ if it's only for ASCII characters, you could use an array<char, 128>, plus an assert, as char might well contain non-ASCII characters. It's important that they might be negative or >127. When using gcc, you can force the default interpretation with -fsigned-char or -funsigned-char. \$\endgroup\$ – jvb Jun 12 '17 at 6:41
10
\$\begingroup\$

A great deal here depends on whether you care more about your code being fast, or being concise to the point of trivial.

For trivially concise code, you could do something like this:

bool all_unique(std::string const &input) { 
    std::set<char> u{input.begin(), input.end()};
    return input.size() == u.size();
}

...or even:

bool all_unique(std::string const &input) { 
    return input.size() == std::set<char> {input.begin(), input.end()}.size();
}

If you're dealing with long input strings, you might gain a bit of speed by using an unordered_set instead:

bool all_unique(std::string const &input) { 
    std::unordered_set<char> u{input.begin(), input.end()};
    return input.size() == u.size();
}

Both of these differ from your solution in one fundamental respect: they both scan the entire input string, even if it does contain duplicates, whereas yours breaks out of the loop at the first duplicate. On a theoretical (big-O) basis, that makes no difference--they're both \$O(n)\$. On a practical basis, it could make a fairly substantial difference.

You might also want to consider handling one trivial case up-front: if the input string is longer than the number of possible characters, then it must contain at least one duplicate.

Regardless of all the preceding points, I would note that I'd much rather see this functionality wrapped up into a clean function as I've done above, rather than having a mixture of code to find whether the characters are unique with the code to print out results and such.

I'd also rather see somewhat more meaningful names. arr and str (for only two examples) aren't really very meaningful. In addition str (and all other names that start with str) is reserved for use by the standard library.

Then there's the obligatory note that while using namespace std; is fairly common in many tutorials and such, it's generally rather frowned upon in normal code. There's room for differences of opinion with respect to using directives for other namespaces, but in the specific case of namespace std, it simply brings an immense number of symbols into scope, where they're free to wreak all sorts of havoc.

\$\endgroup\$
  • 1
    \$\begingroup\$ I didn't think inserting into a set is an O(1) operation. Isn't it O(ln(n)) or worse? That would make this solution much worse than O(n) \$\endgroup\$ – Brandon Jun 11 '17 at 16:18
  • \$\begingroup\$ @Brandon: insertion into a set is log(n), so the overall complexity is O(n log n). For this task big-O analysis isn't really relevant though. Big-O relates to behavior as the number of elements approaches infinity--but in this case, as soon as the number of elements exceeds the size of the character set (255, in the OP's case), we know there has to be at least one duplicate. Ergo, only small N matters, and big-O is mostly irrelevant. \$\endgroup\$ – Jerry Coffin Jun 11 '17 at 16:22
  • 2
    \$\begingroup\$ @Brandon: If you do have a large character set (e.g., Unicode), it actually tends to favor something set-like even more. Assuming a 4-byte int, and a 32-bit character set, the array would end up allocating 16 gigabytes of RAM. In this case, the set-base version will normally finish before the array-based version can allocate the memory to start. \$\endgroup\$ – Jerry Coffin Jun 11 '17 at 16:26
  • 4
    \$\begingroup\$ You are presenting your own solution but where is the review of OPs code? \$\endgroup\$ – zett42 Jun 11 '17 at 17:13
  • 2
    \$\begingroup\$ @zett42 Suggesting alternative (potentially superior) approaches and explaining why they might be preferred still qualifies as code review. \$\endgroup\$ – Pharap Jun 12 '17 at 2:31
4
\$\begingroup\$

Firstly I'm going to be the one to mention the obligatory "using namespace std; is bad".

If you want to be lazy and avoid having to use std:: everywhere, put using namespace std; as the first line of your function (i.e. main).

If you want to be somewhat lazy but also much safer then you can use using to only include the things you are using (and again, declare it within your function so it's local). e.g.

int main()
{
  using std::array;
  using std::cout;
  // The rest of your code
}

You stated the input would be in ASCII yet you have defined an array of 255 characters. ASCII only has 128 characters.

From Wikipedia:

Originally based on the English alphabet, ASCII encodes 128 specified characters into seven-bit integers


Rather than using a C-style const char * it would be better to use a std::string.


You are using an array of char as if it were an array of bool. This is C++, not C - if you want to represent a truth value use bool,true and false, not char,1 and 0.


Your variable names ought to be more representative of the object's function. arr tells me nothing about the purpose of the array, foundCharacters on the otherhand is perfectly self-documenting.


You are not using i outside of the while loop, so your while should be a for.


You really ought to be doing this is a separate function instead of squashing it all into main.


And you may or may not want to use exceptions. Some people avoid them because of concerns about overhead or because they're using embedded systems.


Lastly There is a special case in which you can return early. As you are assuming ASCII as the input encoding, you can return false on cases where the string is longer than the number of possibly valid unique ASCII characters (which is 128). This will also prevent the buffer overrun problem mentioned by @jvb.

Since you are using C style null-terminated const char * instead of C++ style std::string, you can also ignore the null character.


Edit:

As per a suggestion by @Tony Speight, it's possible to use a range-based for loop since the variable i is only being used to iterate the input string.


Applying these changes leaves us with:

#include <iostream>
#include <array>
#include <exception>
#include <string>

bool hasUniqueChars(const std::string & string)
{
    using std::array;
    using std::domain_error;

    if (string.size() > 128)
    {
        return false;
    }

    // using @zett42's suggestion
    array<bool, 128> foundCharacters{};

    // using @Tony Speight's suggestion
    for (const auto c: string)
    {    
        // char may be signed or unsigned so check both possibilities
        if (c < 0 || c > 127)
        {
            // Character is outside the ascii range
            throw domain_error("string had a non-ascii character");
            // return false; if you don't want to use exceptions
        }
        else
        {
            // at is just a precaution as we have already assured c >= 0 and c <= 127
            if (foundCharacters.at(c))
            {
                return false;
            }
            else
            {
                foundCharacters.at(c) = true;
            }
        }
    }

    return true;
}

int main()
{
    using std::string;
    using std::cout;
    using std::domain_error;
    using std::out_of_range;

    const string input = "ABCADEFGHIJKL";

    try
    {
        cout << (hasUniqueChars(input) ? "Unique" : "Not Unique") << '\n';
    }
    catch (const domain_error & error)
    {
        cout << "Invalid input\n";
        cout << error.what();
    }
    catch (const out_of_range & error)
    {
        cout << "Invalid input\n";
        cout << error.what();
    }

    return 0;
}

Note that your 'indexing an array' solution is not viable for larger character sets, in which case @Jerry_Coffin and @Mercury Dime's suggestion of using std::set is a very good one.

Also to make better use of space, a std::bitset would have been better than a std::array.

\$\endgroup\$
  • 1
    \$\begingroup\$ Given you don't use i, why not a range-based loop there? for (const auto c: string) \$\endgroup\$ – Toby Speight Jun 12 '17 at 16:16
  • \$\begingroup\$ @TobySpeight Good point. (To answer why in a roundabout way: I've been working mainly with 8-bit embedded systems recently so I've been avoiding the luxuries of range-based fors and iterators). \$\endgroup\$ – Pharap Jun 12 '17 at 18:47
3
\$\begingroup\$
  1. Think modularly - place code specific to the task inside of a separate function. It will be easier to maintain, and if needed, can be reused in another part of the program (or in a separate program if you add it to a library)

    // Place the code inside of a well named function with the appropriate
    // parameter types and return value (and preferably in a custom namespace so
    // it doesn't collide with other function names)
    bool has_unique_chars(string const& text) { }
    
    int main()
    {
        string str = "Hi";
    
        // Now you can call it from main
        if (has_unique_chars(str))
            cout << "unique\n";
    }
    
    void foo()
    {
        string str = "Where?"
    
        // Or in another function elsewhere in the program
        auto unique = has_unique_chars(str);
    }
    
  2. Use string instead of char*. It's safer and easier to work with.

    // Don't do something like this:
    bool has_unique_chars(const char* text)
    
    // Do this instead:
    bool has_unique_chars(const string& text)
    
    // Or this, if you're using C++17 (potential optimization)
    bool has_unique_chars(string_view text);
    

    See std::string_view in C++17.

  3. When you're trying to solve a problem like this, check to see if there's an existing algorithm in the standard library that solves the problem for you, or at least helps with the solution. When you write your own, you're likely to introduce errors that existing code eliminated a long time ago. In this case, I make use of the find_if() algorithm. It searches a range until an element meeting a specific condition is found. For this problem, the condition is 'a duplicate character'.

  4. Use one of the standard set classes to track unique values instead of an array. The array allocates memory for all characters up front - if the text is only a couple of characters, that's a big waste of space. Sets are made for storing unique values, and since any attempt to insert() an existing value into a set will fail, we can use that knowledge to find duplicates:

    set s = {1,2,3};
    
    // This fails to insert because 3 already exists in the set. The return
    // value is a std::pair, where .second is a boolean indicating whether
    // or not the value was inserted. If it returns false, the value is a
    // duplicate
    if (!s.insert(3).second)
        cout << "duplicate\n";
    

    Solution - Traverse the characters of the string adding each to a set along the way. If an insertion fails, we found a duplicate, and know the string is not made up of unique characters.

  5. There are two issues to think about:

    • what to return for an empty string?
    • how to handle lower/upper case - is 'a' the same as 'A'?

    The code below returns true for an empty string - if you want false, just check for an empty string at the beginning of the function. It also is case sensitive - use tolower() for case insensitive results.

Final Code

// To think about:
// - what about empty strings?
// - what about lower vs upper case?
bool has_unique_chars(const string& text)
{
    // Keep track of the unique characters in the text by using a set
    set<char> charSet;

    // Use the find_if algorithm to find the first duplicate. find_if
    // will iterate until true is returned by the lambda. For this problem
    // the algorithm should stop when a duplicate is found, which is
    // when an insertion into the set fails. set::insert returns .second
    // = false when insertion fails. If there are no duplicates, find_if
    // will return text.end()
    return (std::find_if(text.begin(), text.end(),
        [&charSet](auto ch)
    {
        return !charSet.insert(ch).second;
    }) == text.end());
}
\$\endgroup\$
  • \$\begingroup\$ You are presenting your own solution but where is the review of OPs code? \$\endgroup\$ – WorldSEnder Jun 12 '17 at 1:11
  • \$\begingroup\$ @WorldSEnder Suggesting alternative (potentially superior) approaches and explaining why they might be preferred still qualifies as code review. \$\endgroup\$ – Pharap Jun 12 '17 at 2:35
  • 2
    \$\begingroup\$ Sure, this would be a good answer if it (A) explained in English how the solution worked, and (B) compared and contrasted it to the original solution. A simple code dump is not a quality answer. \$\endgroup\$ – Cody Gray Jun 12 '17 at 10:32
1
\$\begingroup\$

This program looks a lot more like C code than C++.

To write it as more idiomatic C++, I'd start by defining it as a function that takes a std::string:

#include <string>

bool distinct_chars_only(std::string s);

We can then write a simple main() that calls this for each of its command-line arguments; that means we can test without having to re-compile every time:

#include <iostream>
int main(int argc, char **argv)
{
    for (int i = 1;  i < argc;  ++i) {
        std::cout << argv[i] << ": " << (distinct_chars_only(argv[i]) ? "true" : "false") << std::endl;
    }
}

Now, let's implement distinct_chars_only(). We probably want to use std::all_of from <algorithm>, something like

#include <algorithm>
bool distinct_chars_only(std::string s) {
    return std::all_of(s.begin(), s.end(), is_unique);
}

What to use for is_unique? Well, we know that the return value of std::set::insert() tells us whether the item has already been inserted or not - the second element of the pair is true if we see the value for the first time. So we can write:

#include <set>
struct {
    std::set<char> seen = {};
    bool operator()(char c) { return seen.insert(c).second; }
} is_unique;

Full program

#include <algorithm>
#include <set>
#include <string>

bool distinct_chars_only(std::string s) {
    struct {
        std::set<char> seen = {};
        bool operator()(char c) { return seen.insert(c).second; }
    } is_unique;

    return std::all_of(s.begin(), s.end(), is_unique);
}


#include <iostream>
int main(int argc, char **argv)
{
    for (int i = 1;  i < argc;  ++i) {
        std::cout << argv[i] << ": "
                  << (distinct_chars_only(argv[i]) ? "true" : "false")
                  << std::endl;
    }
}
\$\endgroup\$

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.