class Practice1 {
	public static void main(String[] args) {
		// Inspired questions from Cracking the Coding Interview (http://www.amazon.com/dp/098478280X/)
		// CRACKING THE CODING INTERVIEW
		// 1.1 Implement an algorithm to determine if a string has all unique characters.
		// What if you can not use additional data structures?
		// http://asilearneveryday.blogspot.com/2015/01/implement-algorithm-to-determine-if.html
		System.out.println("Has word 'aacd' has unique characters? " + hasUniqueCharactersWithOneInteger("aacd"));
		System.out.println("Has word 'abcd' has unique characters? " + hasUniqueCharactersWithOneInteger("abcd"));
		System.out.println("Has word 'aacd' has unique characters? " + hasUniqueCharactersWithoutAdditionalDataStructures("aacd"));
		System.out.println("Has word 'abcd' has unique characters? " + hasUniqueCharactersWithoutAdditionalDataStructures("abcd"));
		System.out.println("Has word 'aacd' has unique characters? " + hasUniqueCharactersWithDataStructures("aacd"));
		System.out.println("Has word 'abcd' has unique characters? " + hasUniqueCharactersWithDataStructures("abcd"));
	}
	// LOGIC: Uses one integer and checks from 'a' and works for 32 characters.
	// RUNTIME: O(n), where n is the number of characters in the string
	public static boolean hasUniqueCharactersWithOneInteger(String str) {
		int characters=0;
		for(int i =0;i<str.length();i++) {
			int charIntValueFroma = str.charAt(i) - 'a';
			int bitRepresentation = 1<<charIntValueFroma;
			if((characters&bitRepresentation)>0) {
				return false;
			}
			characters |= bitRepresentation;
		}
		return true;
	}
	// LOGIC: Uses two loops to compare a character with every other character.
	// RUNTIME: O(n^2), where n is the number of characters in the string
	public static boolean hasUniqueCharactersWithoutAdditionalDataStructures(String str) {
		for(int i=0;i<str.length();i++) {
			for(int j=i+1;j<str.length();j++) {
				if(str.charAt(i)==str.charAt(j)) {
					return false;
				}
			}
		}
		return true;
	}	
	// LOGIC: Using additional data structures
	// RUNTIME: O(n)
	public static boolean hasUniqueCharactersWithDataStructures(String str) {
		boolean[] characters=new boolean[256];
		for(int i =0;i<str.length();i++) {
			int charIndex = str.charAt(i)-'a';
			if(characters[charIndex]) {
				return false;
			}
			characters[charIndex]=true;
		}
		return true;
	}
}