Using Sorting

• In this solution, we are going to sort the character array of the input String, and then loop through all characters in the array and see if any character matched with previous character. If current and previous characters are same, then String does not have unique characters, otherwise it has unique characters.
• Base case is, if the input String length is 0 or 1, then String has unique characters (as shown in line 5 in below code).

public boolean isStringHasUniqueCharsUsingSorting(String input) { if(input == null) { return false; } if(input.length() == 0 || input.length() == 1) { // if input string is empty or has just one character return true; } char[] chars = input.toCharArray(); Arrays.sort(chars); for(int i=1; i<chars.length; i++) { if(chars[i] == chars[i-1]) { return false; } } return true; } >

Complexity Analysis:

Above code runs in O(n log n) time complexity where n is the size of the array, as we sorting the array. Space complexity is O(n) to store the characters in the array.

Using a HashSet

• In this solution, we are going to loop through the characters of input String, then store each visited character into an intermediate data structure HashSet.
• While looping through each character, check if the same character has already been visited or not by using the method .

public boolean isStringHasUniqueCharsUsingSet(String input) { if(input == null) { return false; } if(input.length() == 0 || input.length() == 1) { // if input string is empty or has just one character return true; } Set<Character> visited = new HashSet<>(); for(int i=0; i<input.length(); i++) { char c = input.charAt(i); boolean duplicateFound = visited.contains(c); if(duplicateFound) { return false; } visited.add(c); } return true; }

Complexity Analysis:

Above code runs in O(n)time complexity where n is the size of the array, as we are looping through characters of the input String and HashSet lookup takes O(1) constant time. Space complexity is O(n) to store the characters in the HashSet.

Using a temporary Array

• In this solution we are going to assume that the input String has only ASCII characters, there are 128 characters in ASCII.
• This solution is very much similar to above solution 2, except that we are using a temp array instead of a Set to keep track of visited characters as we loop through characters of the input String.
• As we loop through each character in the input String, mark corresponding ASCII index in the array with value 1, but if the value at the index is already 1, that means this particular characater is already visited.

public boolean isStringHasUniqueCharsUsingTempArray(String input) { if(input == null) { return false; } if(input.length() == 0 || input.length() == 1) { // if input string is empty or has just one character return true; } int[] visited = new int[128]; for(int i=0; i<input.length(); i++) { char c = input.charAt(i); if(visited[c] != 0) { // this means the same character has already been visited return false; } visited[c] = 1; } return true; }

Note: Please note that if the input String has different character set other than ASCII, then the temp array size need to be adjusted accordingly.

Complexity Analysis:

Above code runs in O(n) time complexity where n is the size of the array, as we are looping through characters of the input String. Space complexity is O(1) as it is a constant size.

One can argue that the Solution 2 also has same Space complexity as Solution 3 if the input String has only ASCII characters and that is true.