Is String Has Unique Characters
Given a string struefalse
Example 1
Output: true
Example 2
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 HashSetaddfalse
Step 3: A fixed array for a small alphabet
If the input is ASCII, there are only 128 possible characters, so a boolean[128]
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"
| Character | Seen before? | Action |
|---|---|---|
| h | no | mark |
| e | no | mark |
| l | no | mark |
| l | yes | return false |
Java Solution
All three methods are below; isUnique
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:
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