Check the Uniqueness of Characters in a String

From Software Engineers Wiki
Jump to: navigation, search

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

Contents

Answer #1

Most simple way is to make use of boolean array to keep track of the usage of each character. Because char type is 8 bits, we allocate an array of 256 entries. char type can be signed. To avoid an issue with signed nature of the char, use unsigned char type instead.

bool isUniqueChar(std::string str)
{
        const unsigned char *cp = (const unsigned char *) str.c_str();
        bool char_used[256] = { };

        while (*cp != '\0') {
                if (char_used[*cp])
                        return false;
                char_used[*cp] = true;
                ++cp;
        }

        return true;
}

Answer #2

Another example using std::bitset<>.

#include <bitset>

bool isUniqueChar(std::string str)
{
        const unsigned char *cp = (const unsigned char *) str.c_str();
        std::bitset<256> char_used; /* default constructor clears all bits */

        while (*cp != '\0') {
                if (char_used.test(*cp))
                        return false;
                char_used.set(*cp);
                ++cp;
        }

        return true;
}

Answer #3

Similar to above solution. Using bitset, but own implementation to minize the memory footprint.

#define bitset32_define_init(bl, bits) \
        uint32_t bl[bits >> 5] = {}
#define bitset32_test(bl, index) \
        (bl[(index) >> 5] & (1 << ((index) & 0x1f)))
#define bitset32_set(bl, index) \
        do { \
                bl[(index) >> 5] = (1 << ((index) & 0x1f)); \
        } while (0)

bool isUniqueChar(std::string str)
{
        const unsigned char *cp = (const unsigned char *) str.c_str();
        bitset32_define_init(char_used, 256);

        while (*cp != '\0') {
                if (bitset32_test(char_used, *cp))
                        return false;
                bitset32_set(char_used, *cp);
                ++cp;
        }

        return true;
}

Answer #4

If the condition is not to use any additional data structure, then we can do O(N^2) approach.

bool isUniqueChar(std::string str)
{
        const unsigned char *cp = (const unsigned char *) str.c_str();
        const unsigned char *cp_next;

        while (*cp != '\0') {
                for (cp_next = cp + 1; *cp_next != '\0'; ++cp_next)
                        if (*cp == *cp_next)
                                return false;
                ++cp;
        }

        return true;
}
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox