Implement an algorithm to determine if a string has all unique characters

Question

I'm working through Cracking the Coding Interview. The first challenge is to implement an algorithm to determine if a string has all unique characters.

I've gone through several iterations, but here's my "final" solution. I've made several assumptions:

1. We are considering case-insensitive strings.
2. We are only considering strings that contain alphabetic characters.
3. We are only considering ASCII strings.

Here's my algorithm and a quick driver. The logic is simple, but I wanted to explain what's going on for sake of the reader.

/*
Implement an algorithm to determine if a string has all unique characters.
What if you can not use additional data structures?
*/

#include <iostream>
#include <string>

bool is_unique(const std::string& s) {
    // seen is a 32-bit bitset. We have seen no letters yet.
    int seen = 0;
    // for every character in the string
    for(auto c: s) {
        // convert the string to lowercase (assumption 1)
        char lower_c = std::tolower(c);
        // normalize the character (assumptions 2 and 3)
        int offset = lower_c - 'a';
        // shift 1 at most 26 to the left. Fits within 32-bit bitset.
        int shifted = 1 << offset;

        if(!(seen & shifted)) {
            // if we haven't seen it, add it to seen
            seen |= shifted;
        } else {
            // otherwise return false -- we have seen it
            return false;
        }
    }
    // if we haven't returned false after the loop, it must be unique
    return true;
}

int main(int argc, char** argv) {
    std::string s{argv[1]};
    std::cout << "Is " << s << " unique? " << is_unique(s) << '\n';
}

Does anyone have recommendations?

Answer 1

Overall this is quite nice piece of source, so only some tiny details here and there (some maybe even ruining it :) )...

From code style perspective I think the variables naming is "only" good, not perfect.

shifted tells what arithmetic operation did happen to the value, which is usually not sought after during reading source. letter_bit_mask sounds to me a bit better.

offset and seen are OK, to be ultra verbose you may still extend them a bit like maybe letter_number and letters_seen, but that's already reaching some tutorial level.

And is_unique itself sounds a bit inexact to me, again a more over-verbose variant like has_unique_letters may be considered.

Can the for work with const auto c? Just for the sake of exercising "putting const everywhere". ;) (I don't believe it will change the machine code produced by compiler). Maybe even reference &?

---

performance ideas (from comment):

If you are already assuming ASCII alphabet-only word inputs, you may do direct int offset = c & 0x1F;, which will yield only 0..31 values, and for 'A'..'Z' vs 'a'..'z' it will produce the same values too (functioning as fake tolower).

I also personally prefer non-else/non-nested if variants (when they make sense), so I would do if (seen & shifted) return false; and the seen |= shifted; would go after that in the for loop block.

This is part of answer is level golfing advice, i.e. lowering readability and robustness of source for some hypothetical performance gain, not suitable for real world production code ;).

---

After applying those suggestions I ended with this:

#include <iostream>
#include <string>

// word must be ASCII letter-only word
// function is case insensitive
bool has_unique_letters(const std::string& word) {
    // seen is a 32-bit bitset. We have seen no letters yet.
    int letters_seen_bit_mask = 0;
    // for every character in the string
    for (const auto & letter: word) {
        // Create bit mask from lower 5 bits of ASCII code.
        // That fits within 32-bit bitset for [a..zA..Z] and
        // will produce same value for 'a' and 'A'.
        int letter_bit_mask = 1 << (letter & 0x1F);

        // If the letter was seen already, return false
        if (letters_seen_bit_mask & letter_bit_mask) return false;

        // if we haven't seen it, add it to seen
        letters_seen_bit_mask |= letter_bit_mask;
    }
    // if we haven't returned false inside the loop, it must be unique
    return true;
}

int main(int argc, char** argv) {
    std::string s{argv[1]};
    std::cout << "Is " << s << " unique? " << has_unique_letters(s) << '\n';
}

Answer 2

If I'd asked an interview question, and got this as an answer (at least as the first answer) I think my immediate reaction would be to consider it excessively clever.

To make much sense, along with the conditions you gave, I'd have had to specify that minimizing memory usage was absolutely crucial.

Under ordinary circumstances, I'd expect an answer something like this:

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

...or something like this:

bool all_unique(std::string input) { 
    std::sort(input.begin(), input.end());
    auto p = std::unique(input.begin(), input.end());
    return p == input.end();
}

There are, of course, variations on these themes (e.g., perfectly reasonable and acceptable to use unordered_set instead of set).

Either of these will work with a much wider range of inputs than you've specified. They will use more storage, but the amount they use is still too small to matter under any normal circumstances.

If somebody were going to craft a special-purpose set of their own, I'd normally expect them to start from std::bitset or std::vector<bool>. I guess if they insisted on starting with a native type to represent their bits, I wouldn't object too terribly much, but I'd be a little disappointed if they chose int for that type.

1. If you want a bag of bits, you should usually use an unsigned type.
2. If you want at least 32 bits, you should use a type that guarantees at least 32 bits (int only guarantees at least 16 bits).

As such, obvious choices would be unsigned long and uint32_t.

Answer 3

Though the variable names could be better, I'm going to focus on data structures and function interfaces in my answer.

Use std::bitset to manage your… well… bit set

The <bitset> header declares the std::bitset class template:

template< std::size_t N >
class bitset;

You would use it like this:

std::bitset<1 << CHAR_BIT> seen;
...
if (seen[c])
  return false;
seen[c] = true;

This implementation can test the uniqueness of all one-byte-characters (but it doesn't need to if you restrict or transform the character set like you do already).

If you want to save a little memory (8 bytes vs. 32 bytes) and gain a little performance (1 shift and 1 AND per look-up if your compiler is smart enough), e. g. because you only want test for uniqueness of case-insensitive ASCII letters, you can restrict the bit set size to 'Z' - 'A' + 1 and do your thing. I doubt that this will have a noticeable impact on performance except for very long strings though.

Use iterators instead of containers to work on sequences

This makes your algorithm much more useful if someone wants to use it on other character sequence containers.

#include <bitset>
#include <string>
#include <iostream>

template <class Iter>
bool is_unique(Iter begin, Iter end) {
    std::bitset<1 << CHAR_BIT> seen;
    for (; begin != end; begin++) {
        char c = *begin;
        ...
        unsigned char uc = static_cast<unsigned char>(c);
        if (seen[uc])
            return false;
        seen[uc] = true;
    }
    return true;
}

int main(int argc, char **argv) {
    std::string s(argv[1]);
    std::cout << is_unique(s.begin(), s.end()) << std::endl;
}

You could even overload the function for null-terminated C strings:

#include <cstring>

bool is_unique(const char *s) {
    return is_unique(s, s + std::strlen(s));
}

int main(int argc, char **argv) {
    std::cout << is_unique(argv[1]) << std::endl;
}

Support arbitrary character types

Since we're using templated iterators already, we can just as well generalize the character types.

#include <bitset>
#include <string>
#include <iterator>
#include <type_traits>
#include <climits>
#include <iostream>

template <class Iter>
bool is_unique(Iter begin, Iter end) {
    typedef typename std::iterator_traits<Iter>::value_type char_type;
    typedef std::char_traits<char_type> char_traits;
    typedef typename std::make_unsigned<typename char_traits::int_type>::type uint_type;

    static_assert(sizeof(char_type) < sizeof(std::size_t));
    std::bitset<std::size_t(1) << sizeof(char_type)*CHAR_BIT> seen;
    for (; begin != end; begin++) {
        char_type c = *begin;
        // ...
        uint_type uc = static_cast<uint_type>(char_traits::to_int_type(c));
        if (seen[uc])
            return false;
        seen[uc] = true;
    }
    return true;
}

template <class CharT>
bool is_unique(const CharT *s) {
    return is_unique(s, s + std::char_traits<CharT>::length(s));
}

Be aware that the bit set will grow very quickly if you use wider character types, e. g. to 8 KiB for wchar_t with 16 bits (Windows) or a whooping 512 MiB for wchar_t with 32 bits (*nix). In those cases you probably want to restrict the tested character subset and/or place the bitset on the heap instead of the stack and/or use an unordered_set that can grow dynamically according to the set of actually occurring characters¹.

---

¹ Using an unordered_set based on character width

Using an unordered_set for large character widths (and alphabets) is smart because a string of length N can hold no more than N different characters, so the the memory consumption of an unordered_set is within \$O(\min\{N, |\Sigma|\})\$ instead of the bitset's \$O(|\Sigma|)\$ (Σ being the alphabet), which means the entire program only needs up to \$O(N + \min\{N, |\Sigma|\}) = O(N)\$ memory units (one additional N for the input).

You can use partial template specialization to use either bitset or unordered_set based on the character width like this:

#include <bitset>
#include <unordered_set>
#include <string>
#include <iterator>
#include <type_traits>
#include <climits>
#include <iostream>
#include <locale>
#include <codecvt>

#define MAX_STATIC_CHARSET_SIZE (8 << 20)

template <class CharT, bool StaticSetSize>
class my_charset_impl;

template <class CharT>
class my_charset_impl<CharT, true> {
private:
    typedef CharT char_type;
    typedef std::char_traits<char_type> char_traits;
    typedef typename std::make_unsigned<typename char_traits::int_type>::type uint_type;

    static_assert(sizeof(char_type) < sizeof(std::size_t));
    std::bitset<std::size_t(1) << sizeof(char_type)*CHAR_BIT> _set;

public:
    bool insert(char_type c) {
        auto entry_ref = _set[static_cast<uint_type>(char_traits::to_int_type(c))];
        if (entry_ref)
            return false;
        entry_ref = true;
        return true;
    }
};

template <class CharT>
class my_charset_impl<CharT, false> {
private:
    typedef CharT char_type;

    std::unordered_set<char_type> _set;

public:
    bool insert(char_type c) {
        return _set.insert(c).second;
    }
};

template <class CharT>
using my_charset = my_charset_impl<CharT, sizeof(my_charset_impl<CharT, true>) <= MAX_STATIC_CHARSET_SIZE>;

template <class Iter>
bool is_unique(Iter begin, Iter end) {
    typedef typename std::iterator_traits<Iter>::value_type char_type;
    my_charset<char_type> seen;
    for (; begin != end; begin++) {
        char_type c = *begin;
        // ...
        if (!seen.insert(c))
            return false;
    }
    return true;
}

template <class CharT>
bool is_unique(const CharT *s) {
    return is_unique(s, s + std::char_traits<CharT>::length(s));
}

int main(int argc, char **argv) {
    std::string s(argv[1]);
    std::cout << is_unique(s.cbegin(), s.cend()) << std::endl;

    std::cout << is_unique(argv[1]) << std::endl;

    std::u32string ws = std::wstring_convert<std::codecvt_utf8<char32_t>, char32_t>().from_bytes(s);
    std::cout << is_unique(ws.cbegin(), ws.cend()) << std::endl;
}

This example calls is_unique three times,

1. with const char *,
2. with std::string::iterator_type, and
3. with std::u32string::iterator_type, where the u32string instance contains the UTF-32 representation of argv[1].

Answer 4

    // for every character in the string
    for(auto c: s) {

I would hope that anyone evaluating your code would be able to figure out that for (auto c: s) means "for every character in the string". You shouldn't have to comment that. If anything, consider giving s a more descriptive name to make that clearer. Why save letters on a short name when you just waste them on a comment instead?

        if(!(seen & shifted)) {
            // if we haven't seen it, add it to seen
            seen |= shifted;
        } else {
            // otherwise return false -- we have seen it
            return false;
        }

I prefer not to put an else on an if that is a negative. I'd rather flip it around.

        if (seen & shifted) {
            // return false -- we have seen it
            return false;
        } else {
            // if we haven't seen it, add it to seen
            seen |= shifted;
        }

But if we do that, we don't need the else.

        if (seen & shifted) {
            // we found a duplicate letter, so not all unique
            return false;
        }

        // mark as seen
        seen |= shifted;

We don't need it for two reasons. First, we're returning, so we'll never reach the other code when the else would not have triggered. Second, it doesn't matter. We can run the last statement regardless, because if seen & shifted is true, then seen == seen | shifted is already true. We just need to make sure that we test if it is present before we add it.

That suggestion was already made, but my reasons are different.

As a general rule, try to make your comments relate to the problem more than the code. You don't need to tell us that you're returning false, we can see that. Concentrate on explaining what false means in that context. In this case, that's that there is a letter that appears more than once.

It probably won't matter for this interview, but I would have included the three assumptions in the comments. You refer to them, but you don't include them.

Even better, write unit tests and assertions that cover the comments. Since unit tests are code, failing them produces errors. Comments that don't match the code require a human being to discover them and act on them. Unit tests only require running the tests, not line by line inspection. I can tell you that unit tests written in an interview will usually do more for you than algorithmic cleverness.