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 <iostream>
#include <string>
#include <map>
using namespace std;
// Uses an iterator to display the map.
void displayMap(map<char, int> displayCharacters)
{
for (map<char, int>::iterator itr = displayCharacters.begin(), end = displayCharacters.end(); itr != end; ++itr)
{
cout << itr->first << " --> " << itr->second << endl;
}
}
// Checks for uniqueness for a given string and returns a boolean.
bool isUnique(int stringLength, string alphabet, map<char, int> uniqueCharacters)
{
for (int i = 0; i < 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<char, int> readString(string stringRead, map<char, int> uniqueCharacters)
{
for (int i = 0, strLen = stringRead.length(); i < 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<char, int> 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 << "Unique string!\n";
}
else
{
cout << "Not unique!\n";
}
cin.ignore();
cin.get();
}
