Uniqueness.cpp

/* Problem 1.1: Implement an algorithm to determine if a string 
 * has all unique characters. What if you cannot use additional
 * data structures?
 * @author: Rafayel Mkrtchyan
 * @date:   9/13/2015
 */

#include <iostream>
#include <algorithm>

/* This solution uses an additional data structure -
 * array of boolean values that has 256 elements.
 * The speed of this solution is O(n).
 */
bool is_unique_usingMemory(std::string str) {
    bool UniquenessChecker[256] = {false};
    for (int index = 0; index < str.length(); index++) {
        int value = str[index];
        if (UniquenessChecker[value] == true) {
            return false;
        }
        UniquenessChecker[value] = true;
    }
    return true;
}

/* This solution uses no additional data structures.
    However, the speed of this one is O(NlogN).
*/

bool is_unique_noMemory(std::string str) {
    std::sort(str.begin(), str.end());
    for (int index = 0; index < str.length() - 1; index++) {
        if (str[index] == str[index + 1]) {
            return false;
        }
    }
    return true;
}

int main () {
    std::string str1 = "Berkeley";
    bool first1 = is_unique_usingMemory(str1);
    bool first2 = is_unique_noMemory(str1);
    std::cout << first1 << " " << first2 << std::endl;
    std::string str2 =  "Stanford";
    bool second1 = is_unique_usingMemory(str2);
    bool second2 = is_unique_noMemory(str2);
    std::cout << second1 << " " << second2 << std::endl;
    std::string str3 = "Columbia";
    bool third1 = is_unique_usingMemory(str3);
    bool third2 = is_unique_usingMemory(str3);
    std::cout << third1 << " " << third2 << std::endl;
    std::string str4 = "Harvard";
    bool fourth1 = is_unique_noMemory(str4);
    bool fourth2 = is_unique_usingMemory(str4);
    std::cout << fourth1 << " " << fourth2 << std::endl;
    return 0;
}