<Check then Change> pattern (Unique string problem, uses bit vector)

One of the very first Cracking The Coding Interview question is to write a function that checks if a string is made up of totally unique characters.

 

public void isUniqueString(String str){
	boolean record = new boolean[128];
    for(int i = 0; i<str.length(); i++){
    	int val = str.charAt(i);
        if(record[str.charAt(i)] == true){
        	return false;
        }
        record[str.charAt(i) = true;
    }
}

However, bit vector method works like this:

public boolean isUniqueString(String str){
	//bit vector
    int record = 0;
    
    for(int i = 0; i<str.length(); i++){
    	// normalize the index for bit vector
        int val = str.charAt(i) - 'a';
        
        // detect duplicate, and return false
        if(record&&(1<<val)>0){
        	return false;
        }        
        
    	// record to the bit vector
        record |= (1<<val);
        
    }
    

}

Note the pattern; the part where record bit vector is modified is at the END of the iteration, not at the start; the part that checks the duplicate is before that modification part. This is because in the first iteration, the control doesn't get affected by the condition check logic, and arrives at the modification part. And you can imagine that the check will be done correctly from that point on.