Solutions for Cracking the Coding Interview

public static boolean isUniqueChars(String str) {
	boolean[] char_set = new boolean[256];
	for (int i = 0; i < str.length(); i++) {
		int val = str.charAt(i);
		if (char_set[val]) return false;
		char_set[val] = true;
	}
	return true;
}
time: O(n)
space: O(n)

public static boolean isUniqueChars(String str) {
	int checker = 0;
	for (int i = 0; i < str.length(); ++i) {
		int val = str.charAt(i) - 'a';
		if((checker & (1 << val)) > 0) return false;
		checker |= (1 << val);
	}
	return true;
}
Alternatively, we could do the following:
1. Check every char of the string with every other char of the string for duplicate occurences. This will take O(n^2) time and no space;
2. If we are allowed to destroy the input string, we could sort the string in O(n log n) time and then linearly check the string for neighboring characters that are identical. Careful, though - many sorting algorithms take up extra space.

void reverse(char *str) {
	char * end = str;
	char tmp;
	if (str) {
		while (*end) {
			++end;
		}
		--end;
		while (str < end) {
			tmp = *str;
			*str++ = *end;
			*end-- = tmp;
		}
	}
}

public static void removeDuplicates(char[] str) {
	if (str == null) return;
	int len = str.length;
	
	int tail = 1;
	
	for (int i = 1; i < len; ++i) {
		int j;
		for (j = 0; j < tail; ++j) {
			if (str[i] == str[j]) break;
		}
		if(j == tail) {
			str[tail] = str[i];
			++tail;
		}
	}
	str[tail] = 0;
}

Test case:
1. String does not contain any duplicates, e.g.: abcd
2. String contains all duplicates, e.g.: aaaa
3. Null string
4. String with all continuous duplicates, e.g.:aaabbb
5. String with non-contiguous duplicates, e.g.: abababa

public static void removeDuplicatesEff(char[] str) {
	if (str == null) return;
	int len = str.length;
	if (len < 2) return;
	boolean[] hit = new boolean[256];
	for (int i = 0; i < 256; ++i) {
		hit[i] = false;
	}
	hit[str[0]] = true;
	int tail = 1;
	for (int i = 1; i < len; ++i) {
		if (!hit[str[i]]) {
			str[tail] = str[i];
			++tail;
			hit[str[i]] = true;
		}
	}
	str[tail] = 0;
}
Test cases:
1. String does not contain any duplicates, e.g. :abcd
2. String contains all duplicates, e.g. : aaaa
3. Null string
4. Empty string
5. String with all continuous duplicates, e.g. : aaabbb
6. String with non-contiguous duplicates, e.g. : abababa