CrackingTheCodingInterview_6th_Solution

1_1isUnique

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

/*
One solution is to create an array of boolean values, where the flag at index i indicates
whether character i in the alphabet is contained in the string.
We can also immediately return false if the string length exceeds the number of unique
characters in the alphabet.

The time complexity for this solution is O(n), where n is the length of the string.
The space complexity is O(1).
*/

#include <iostream>
#include <string>
#include <bitset>
#include <vector>
#include <algorithm>
using namespace std;

bool isUnique1(string s) {
	//overall 128 characters
	if(s.length() > 128) return false;
	
	bool count[128];
	for(int i=0; i<128; i++) count[i] = false;
	
	for(int i=0; i<s.length(); i++) {
		int idx = s[i];
		if(count[idx]) return false;
		count[idx] = true;
	}
	return true;
}


/*
We can reduce out space usage by a factor of 8 by using a bit vector.
*/
bool isUnique2(string s) {
	bitset<128> count;
	
	for(int i=0; i<s.length(); i++) {
		int idx = s[i];
		if(count.test(idx) == true) return false;
		count.set(idx);
	}
	return true;
	
}

/*
If we can't use additional data structure:
1. 	Compare every character of the string to every other character of the string.
	This will take O(n^2) time and O(1) space.
2.	If we are allowed to modify the inpute string, we could sort the string in O(n log(n))
	time and then linealy check the string for neighboring characters that are identical
*/
bool isUnique3(string s) {
	int i, j;
	for(i=0; i<s.length(); i++) {
		for(j=i+1; j<s.length(); j++) {
			if(s[i]==s[j]) return false;
		}
	}
	return true;
}

bool isUnique4(string s) {
	sort(s.begin(), s.end());
	for(int i=1; i<s.length(); i++) {
		if(s[i] == s[i-1]) return false;
	}
	return true;
}

//Testing
int main() {
	
	string str1 = "abcde";
	string str2 = "hello";
	
	bool strUnique11 = isUnique1(str1);
	bool strUnique12 = isUnique2(str1);
	bool strUnique13 = isUnique3(str1);
	bool strUnique14 = isUnique4(str1);
	bool strUnique21 = isUnique1(str2);
	bool strUnique22 = isUnique2(str2);
	bool strUnique23 = isUnique3(str2);
	bool strUnique24 = isUnique4(str2);
	
	cout << strUnique11 << endl;
	cout << strUnique12 << endl;
	cout << strUnique13 << endl;
	cout << strUnique14 << endl;
	cout << strUnique21 << endl;
	cout << strUnique22 << endl;
	cout << strUnique23 << endl;
	cout << strUnique24 << endl;
	
	return 0;	
	
}