Comparison of these two algorithms?

Question

So I'm presented with a problem that states. "Determine if a string contains all unique characters"

So I wrote up this solution that adds each character to a set, but if the character already exists it returns false.

private static boolean allUniqueCharacters(String s) {

    Set<Character> charSet = new HashSet<Character>();
    for (int i = 0; i < s.length(); i++) {
        char currentChar = s.charAt(i);
        if (!charSet.contains(currentChar)) {
            charSet.add(currentChar);

        } else {
            return false;
        }

    }
    return true;

}

According to the book I am reading this is the "optimal solution"

public static boolean isUniqueChars2(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;
}

My question is, is my implementation slower than the one presented? I assume it is, but if a Hash look up is O(1) wouldn't they be the same complexity?

Thank you.

Answer 1

As Amadan said in the comments, the two solutions have the same time complexity O(n) because you have a for loop looping through the string, and you do constant time operations in the for loop. This means that the time it takes to run your methods increases linearly with the length of the string.

Note that time complexity is all about how the time it takes changes when you change the size of the input. It's not about how fast it is with data of the same size.

For the same string, the "optimal" solution should be faster because sets have some overheads over arrays. Handling arrays is faster than handling sets. However, to actually make the "optimal" solution work, you would need an array of length 2^16. That is how many different char values there are. You would also need to remove the check for a string longer than 128.

This is one of the many examples of the tradeoff between space and time. If you want it to go faster, you need more space. If you want to save space, you have to go slower.

Answer 2

Both algorithms have time complexity of O(N). The difference is in their space complexity.

The book's solution will always require storage for 128 characters - O(1), while your solution's space requirement will vary linearly according to the input - O(N).

The book's space requirement is based on an assumed character set with 128 characters. But this may be rather problematic (and not scalable) given the likelihood of needing different character sets.