0
\$\begingroup\$

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) {

            if (text == null || text.isEmpty()) {
                return false;
            }

            //only one char has to be unique
            if (text.length() == 1) {
                return true;
            }

            HashSet<Character> textChars = new HashSet<>();

            for (char c : text.toCharArray()) {
                if (textChars.contains(c)) {
                    return false;
                }
                textChars.add(c);
            }
            return true;
        }


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

        public static boolean hasUniqueChars2(String text) {

            if (text == null || text.isEmpty()) {
             return false;
            }

            //only one char has to be unique
            if (text.length() == 1) {
             return true;
            }
            //nested loop to check
            for (int i = 0; i < text.length(); i++) {
                for (int j = 0; i < text.length(); j++) {
                    if (i != j && text.charAt(i) == text.charAt(j)) {
                        return false;
                    }
                }
            }
            return true;
        }


        public static void main(String... args) {

            System.out.println(hasUniqueChars("test123"));
            System.out.println(hasUniqueChars2("test123"));
        }
    }
\$\endgroup\$
0

1 Answer 1

3
\$\begingroup\$

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) {

        if (text == null || text.isEmpty()) {
         return false;
        }

        char[] chars = text.toCharArray();
        Arrays.sort(chars);
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == chars[i - 1]) {
                return false;
            }
        }
        return true;
    }
\$\endgroup\$
1
  • \$\begingroup\$ thanks for your comments and recommendation! I have fixed the bug and updated the review..I had run the second option for a false case only and did not notice it! \$\endgroup\$ Commented Jul 13, 2018 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.