1.1 Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?

TestUnique.java

public class TestUnique {

	/* use a array to record the occurrence of different characters
	 * first method uses extra space
	 * NOTE: the spaces will cause duplicates too
	 * the time complexity is O(n), the space complexity is also O(n)
	 */
	public static boolean test(String input){
		boolean char_set[] = new boolean[255]; 
		
		for(int i = 0; i < input.length(); i++){
			int index = input.charAt(i);       // implicit conversion from char to int 
			if(char_set[index])
				return false;
			char_set[index] = true;
		}
		return true;
	}
	
	
	 /* first use quicksort to sort the input O(nlogn)
	  * then iterate the sorted array to check if there are duplicates O(n)
	  * so the total running time is O(nlogn) + O(n) = O(nlogn);
	  */
	public static boolean test2(String input){
		char[] data = input.toCharArray();
		quickSort(data, 0, data.length-1);
		
		for(int i = 0; i < data.length -1; i++)
			if(data[i] == data[i+1])
				return false;
		return true;
	}
	
	
	public static void quickSort(char[] data, int left, int right){
		if(right - left > 0){
			int pivot = partition(data, left, right);
			quickSort(data, left, pivot - 1);
			quickSort(data, pivot + 1, right);
		}
	}
	
	public static int partition(char[] data, int left, int right){
		int pivot = data[left];
		char temp;
		int i = left + 1;
		
		for(int j = left + 1; j <= right; j++){
			if(data[j] < pivot){
				temp = data[j];
				data[j] = data[i];
				data[i] = temp;
				i++;
			}
		}
		
		temp = data[i-1];
		data[i-1] = data[left];
		data[left] = temp;
		
		return i - 1;
	}
}