Checking for uniqueness within a string I saw this interview question in the book Cracking the Coding Interview:


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


The authors solution uses bit-shifting for a pretty efficient solution. 

I wanted to give it a shot to discover some new things and practice some. I'd like for this to be a discussion of how I can improve my programming and also, what the correct answer may be. Did I leave out any edge-cases? Is there a more efficient way of doing this?

#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;map&gt;

using namespace std;

// Uses an iterator to display the map.
void displayMap(map&lt;char, int&gt; displayCharacters)
{
    for (map&lt;char, int&gt;::iterator itr = displayCharacters.begin(), end = displayCharacters.end(); itr != end; ++itr)
    {
        cout &lt;&lt; itr-&gt;first &lt;&lt; " --&gt; " &lt;&lt; itr-&gt;second &lt;&lt; endl;
    }
}

// Checks for uniqueness for a given string and returns a boolean.
bool isUnique(int stringLength, string alphabet, map&lt;char, int&gt; uniqueCharacters)
{
    for (int i = 0; i &lt; stringLength; i++)
    {
        if (uniqueCharacters[alphabet[i]] == 1)
        {
            return false;
        }

        uniqueCharacters[alphabet[i]]++;
    }

    return true;
}

// Maps individual characters found in stringRead and sets a value to them.
// Returns the mapped map.
map&lt;char, int&gt; readString(string stringRead, map&lt;char, int&gt; uniqueCharacters)
{
    for (int i = 0, strLen = stringRead.length(); i &lt; strLen; i++)
    {
        uniqueCharacters[stringRead[i]] = 0;
    }

    return uniqueCharacters;
}

int main()
{
    // Create a map to store a key character and value int. 
    // Create a string to hold a variable string to test.
    map&lt;char, int&gt; uniqueCharacters;
    string testString = "aaabbbccc";
    int stringLength = testString.length();

    // uniqueCharacters is mapped to the above string and the displayed using displayMap.
    uniqueCharacters = readString(testString, uniqueCharacters);
    displayMap(uniqueCharacters);

    if (isUnique(stringLength, testString, uniqueCharacters))
    {
        cout &lt;&lt; "Unique string!\n";
    }
    else
    {
        cout &lt;&lt; "Not unique!\n";
    }

    cin.ignore();
    cin.get();
}
This solution is inefficient:


There is no point counting the characters in the entire string: once you found a duplicate, you can stop counting, because you know the result is false


This also implies that the map of counts is wasted space

Iterating over the alphabet to check character counts is inefficient: it would be better to iterate over the map values


Instead of a map, it would be more efficient to use a set.

Instead of a set, you could also consider a boolean array of the size of the alphabet, values initialized to false,
and use that to track characters seen so far.
The disadvantage of this approach over a set is that it might use more space.

You are also violating some good practices:


using namespace std is considered bad practice
readString is poorly named: it doesn't "read a string", it initializes a map of character counts to all zero values
No need to pass stringLength together with testString. You can derive that value from testString