Is String Has Unique Characters

Given a string s, return true if every character in it is different, and false if any character appears more than once. This is a classic interview question, often asked with the follow-up "what if you cannot use extra data structures?".

Example 1
Input: s = "square"
Output: true
Example 2
Input: s = "hello"
Output: false
Explanation: "l" appears twice.

How to Think About It

Step 1: Sort, then look at neighbours

After sorting the characters, any repeated character sits right next to its copy. One pass comparing neighbours finds it. This takes O(n log n) time and works without any set or map, which answers the follow-up.

Step 2: Remember what you have seen

Walk through the string and add each character to a HashSet. If add returns false, the character was already there. This is O(n) and works for any characters, including Unicode.

Step 3: A fixed array for a small alphabet

If the input is ASCII, there are only 128 possible characters, so a boolean[128] does the job of the set, faster and with constant space.

The same limit gives a free shortcut: a string longer than 128 ASCII characters must repeat one (the pigeonhole principle), so it can be rejected without looking at it.

Walkthrough

The array method on s = "hello".

CharacterSeen before?Action
hnomark
enomark
lnomark
lyesreturn false

Java Solution

All three methods are below; isUnique is the array version.

Java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class IsStringHasUniqueCharacters {

    // 1. Sorting: equal characters end up next to each other. O(n log n)
    public static boolean isUniqueBySorting(String s) {
        char[] c = s.toCharArray();
        Arrays.sort(c);
        for (int i = 1; i < c.length; i++) {
            if (c[i] == c[i - 1]) {
                return false;
            }
        }
        return true;
    }

    // 2. HashSet: works for any characters. O(n) time, O(n) space
    public static boolean isUniqueBySet(String s) {
        Set<Character> seen = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (!seen.add(c)) {
                return false;
            }
        }
        return true;
    }

    // 3. Fixed array: for ASCII input. O(n) time, O(1) space
    public static boolean isUnique(String s) {
        if (s.length() > 128) {
            return false;                     // more characters than there are ASCII values
        }
        boolean[] seen = new boolean[128];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (seen[c]) {
                return false;
            }
            seen[c] = true;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isUnique("square") + " " + isUniqueBySet("square")
                + " " + isUniqueBySorting("square"));   // true true true
        System.out.println(isUnique("hello") + " " + isUniqueBySet("hello")
                + " " + isUniqueBySorting("hello"));    // false false false
    }
}

The original implementation and its tests are on GitHub: IsStringHasUniqueCharacters.java and TestIsStringHasUniqueCharacters.java.

Complexity

  • Sorting: O(n log n) time, O(n) for the character array (O(1) if sorting in place is allowed).
  • HashSet: O(n) time, O(n) space.
  • Fixed array: O(n) time, O(1) space (128 entries, whatever the input length).

For lowercase letters only, one int can replace the array, using one bit per letter, as in Optimal Partition of String.