[Array and Strings] CCI 1.1

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

 

1) Brute Force (I made this not to use additional data structure)

Calculate each item by iterating the string >> result in O(n^2)

boolean isUnique(String[] string){
	for (int i = 0; i < string.length; i++){
    //Since we compute one for i we don't have to start from i again.
    	for (int j = 0; j < string.length; j++){
        	if (i != j){ //since we don't have to compare in the same character
                if (string[i] == string[j]){
                    return false;
                }
            }
        }
    }
    return true;
}

2) Optimize

boolean isUnique(String[] string){
	for (int i = 0; i < string.length; i++){
    //Since we compute one for i we don't have to start from i again.
    	for (int j = i; j < string.length; j++){
        	if (i != j){ //since we don't have to compare in the same character
                if (string[i] == string[j]){
                    return false;
                }
            }
        }
    }
    return true;
}

Since we checked i, we don't have to check that character. This will still be O(n^2) though.

 

Answer:

You should first ask your interviewer if the string is an ASCII string or a Unicode string. Asking this question will show an eye for detail and a solid foundation in computer science. We'll assume for simplicity the character set is ASCII. If this assumption is not valid,we would need to increase the storage size.

 

If you cannot use additional data structure:

1. Compare every character of the string to every other character of the string. This will take O(n
^2) time and O(1) space. (Which I implemented and reduced time)

 

2. If we are allowed to modify 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. (Caution: many sorting algorithms take up extra space)

 

Optimized Solution for using other Data Structure:

boolean isUniqueChars(String str) {
	if (str.length() > 128) return false;
    
    boolean[] char_set = new boolean[128];
    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;
}

This function works in O(n). The space complexity is O(1). You could also argue that the time complexity is O(1), since the for loop will never iterate through more than 128 characters.) If you didn't want to assume the character set is fixed, you could express the complexity as O(c) space and O(min()c, n)) or O(c) time, where c is the size of the character set.