trjhtr

Two solutions to check if a String contains unique characters.
Wanted to know if these solutions can be optimized further.

The Code:

 public class UniqueCharactersInString 


 //running time O(N) and O(N) space
 public static boolean hasUniqueChars(String text) 


 //running time O(N ^ 2) and O(1) space

 public static boolean hasUniqueChars2(String text) 

 if (text == null 


 public static void main(String... args) 

 System.out.println(hasUniqueChars("test123"));
 System.out.println(hasUniqueChars2("test123"));
 
 

Both solutions

Both your solutions check for text.lenght() == 1. This is not really much of an optimization and it makes it seem like it is a special case, but your code will do just fine without that check. Remove it.

First solution

Your first solution using a HashSet can be improved by using the return value of the add(...) method, which is true if the value is added, and false if the value was already there. See the documentation

This allows you to simplify the inner condition from:

 if (textChars.contains(c)) 
 return false;
 
 textChars.add(c);

to

 if (!textChars.add(c)) 
 return false;
 

In general, while your complexity assessments are accurate, there is a significant amount of space involved in converting char to Character instances and then the overheads of the HashSet are significant. I imagine for even reasonably large strings, it will be slower than your second option... which also has problems.

Second solution

This solution is neatly written, but has a significant performance issue. Instead of the j loop running from 0 to text.length() it can instead run from 0 to i. The solution you currently have compares many values redundantly (for example, in the word hello it will compare h to e and also e to h)

The resulting code would look like:

 //nested loop to check
 for (int i = 0; i < text.length(); i++) 
 for (int j = 0; j < i; j++) 
 if (text.charAt(i) == text.charAt(j)) 
 return false;
 
 
 

Bug

While answering this section, though, I see your code actually has a bug, which irritates me, because this has to be something you have seen..... your code's j loop looks like:

for (int j = 0; i < text.length(); j++) {

and that contains the condition i < text.lenght() instead of j < text.lenght().... so you have an infinite loop. Your code is broken. If you had run this code, you would know that....

My recommendation

... is for a 3rd option to try. You should get the characters in an array, and then sort them, and compare neighbours....

for example:

 //running time O(N log(N)) and O(N) space
 public static boolean hasUniqueChars3(String text)