package khan.cube.rootcampalgos.agorithms.uniquestring;

import java.util.HashSet;
import java.util.Set;

/**
 * Loop over the input and keep track of characters in hash set to identify duplication.
 * 
 * Complexity - Time: o(n), n is the length of input string
 * Complexity - Space: o(c), c is the number of distinct characters in input
 * 
 * Pros: No restriction on string size.
 * 	   : Linear time complexity.
 * 
 * Cons: Need an extra space for hash set.
 * 
 * @author SDK
 *
 */
public class SetBasedAlgorithm implements UniqueString{

	public boolean isUnique(String inputString) {
		boolean unique=true;
		Set<Character> charSet = new HashSet<Character>(inputString.length());
		for(int i=0;i<inputString.length();i++) {
			Character charValue = inputString.charAt(i);
			if(charSet.contains(charValue)) {
				unique = false;
				break;
			}
			else
				charSet.add(charValue);
		}
		return unique;
	}
}
