Check Whether All Characters in a String Are Unique - Java

Category: Easy/Medium | Concepts used: Hash-set lookup, frequency tracking, bitmasking, Pigeonhole Principle

---

Problem Statement

Given a string, check whether all characters are unique (no character repeats).

Input : "abcdef"     Output: true    (all unique)
Input : "hello"       Output: false   ('l' repeats)

Examples (with edge scenarios)

#	Input	Output	Why
1	"abcdef"	true	Each letter appears exactly once
2	"hello"	false	'l' appears twice
3	""	true	Empty string has no repeats (vacuously unique)
4	"a"	true	Single character is unique
5	"AaBb"	Clarify	If case-sensitive → true. If case-insensitive → false. Always clarify this constraint.

⚠️ Common Beginner Mistake

Mistake	Impact	Fix
Writing a nested-loop brute force comparing indices without stating its cost	Sub-optimal (O(N^2)) performance	Proactively state that it can be optimized to (O(N)) using a hash-set
Forgetting charset boundaries	Wastes CPU time on long strings	Apply the Pigeonhole Principle early check

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm how null and empty strings should behave, whether comparison is case-sensitive, and whether spaces or punctuation count. Java char values are UTF-16 code units, not always complete human-visible Unicode characters, so international text may require code points or grapheme-aware libraries.

Analogy: Guest List Registry

Imagine you are a receptionist checking guests into a hotel conference:

• Solution 1 (Brute Force): For every guest who walks in, you look at their badge and then walk around the entire room comparing their badge against every single person already in the room. This is extremely slow and tires you out quickly.
• Solution 2 (HashSet): You keep a blank clipboard registry. When a guest walks in:
  • You check if their name is already written on the paper.
  • If it is, you know they’ve already checked in (return false).
  • If it isn’t, you write their name down (seen.add(ch)) and let them in.
• Pigeonhole Principle: If there are 256 guest rooms (maximum possible ASCII values) and 300 guests check in, you know without looking at a single name that at least two guests must be sharing a room!

---

Solution 1 — Brute Force with Nested Loops

This is the baseline (O(N^2)) approach comparing pairs.

Intuition

Compare every character at index i against every subsequent character at index j. If a match is found, returns false early.

public class UniqueCharsBruteForce {
    public static boolean allUnique(String str) {
        if (str == null) return false;

for (int i = 0; i < str.length(); i++) {
            for (int j = i + 1; j < str.length(); j++) {
                if (str.charAt(i) == str.charAt(j)) {
                    return false; // Found duplicate
                }
            }
        }
        return true;
    }

public static void main(String[] args) {
        System.out.println(allUnique("abcdef")); // true
        System.out.println(allUnique("hello"));    // false
        System.out.println(allUnique(""));          // true
    }
}

Output:

true
false
true

---

Solution 2 — Using a HashSet (Recommended)

This is the optimal (O(N)) approach using a lookup set.

Intuition

A HashSet allows constant-time (O(1)) lookups. By checking if the set already contains the current character before inserting it, we find duplicates immediately.

import java.util.HashSet;

public class UniqueCharsHashSet {
    public static boolean allUnique(String str) {
        if (str == null) {
            return false;
        }

// Pigeonhole Principle Optimization (Assuming Extended ASCII range 256)
        if (str.length() > 256) {
            return false;
        }

HashSet<Character> seen = new HashSet<>();
        for (char ch : str.toCharArray()) {
            if (seen.contains(ch)) {
                return false; // Found duplicate
            }
            seen.add(ch);
        }
        return true;
    }

public static void main(String[] args) {
        System.out.println(allUnique("abcdef")); // true
        System.out.println(allUnique("hello"));    // false
    }
}

---

Solution 3 — Bit Manipulation (Advanced)

An optimal (O(1)) space solution using a bitmask, limited to lowercase English letters (a-z).

Intuition

We use a single 32-bit integer checklist as our bit vector (since English lowercase has 26 letters, fitting in 32 bits). Each bit position represents a letter. By shifting 1 by the character’s relative position (ch - 'a'), we check if that bit is already flipped using bitwise AND (&).

public class UniqueCharsBitmask {
    public static boolean allUnique(String str) {
        if (str == null) return false;
        if (str.length() > 26) return false; // More than 26 chars must contain duplicates (a-z)

int checklist = 0; // 32-bit bitmask register

for (char ch : str.toCharArray()) {
            int bitPosition = ch - 'a'; // Map 'a' -> 0, 'b' -> 1...
            int mask = 1 << bitPosition;

if ((checklist & mask) != 0) {
                return false; // Bit is already set to 1 (duplicate seen)
            }
            checklist |= mask; // Set the bit to 1
        }
        return true;
    }

public static void main(String[] args) {
        System.out.println(allUnique("abcdef")); // true
        System.out.println(allUnique("hello"));    // false
    }
}

---

📊 Visual Flowchart

graph TD
    Start["Input String S"] --> NullCheck{"S is null?"}
    NullCheck -->|Yes| RetFalse["Return False"]
    NullCheck -->|No| Pigeon{"S.length() > 256?"}
    Pigeon -->|Yes| RetFalse2["Return False (Pigeonhole Principle)"]
    Pigeon -->|No| InitSet["Initialize HashSet seen"]
    InitSet --> Loop{"i < S.length()?"}
    Loop -->|Yes| Fetch["ch = S.charAt(i)"]
    Fetch --> CheckSet{"seen.contains(ch)?"}
    CheckSet -->|Yes| Dup["Return False"]
    CheckSet -->|No| Insert["seen.add(ch)"]
    Insert --> IncLoop["i++"]
    IncLoop --> Loop
    Loop -->|No| End["Return True"]

---

Interviewer Insights

This question tests algorithmic optimization, bounds logic, and bitwise arithmetic.

Follow-up questions you might get:

• “What is the Pigeonhole Principle early exit check?” → Explain that if the character encoding set has a maximum size (e.g. 256 for Extended ASCII, 128 for Basic ASCII), any input string longer than that maximum size must contain at least one duplicate. Adding this simple boundary check short-circuits the method to (O(1)) worst-case time for long inputs.
• “Why is the bitwise mask solution space-optimal?” → The HashSet solution allocates objects in the heap memory taking (O(N)) space. The bitwise mask solution fits entirely in a single 32-bit register on the CPU stack, operating in (O(1)) auxiliary memory.

---

Quick Recap

Approach	Time Complexity	Auxiliary Space Complexity	Handles All Characters?	Interview Signal
Brute Force	(O(N^2))	(O(1))	Yes	Basic, requires optimization
HashSet	(O(N))	(O(K)) (where (K \le 256))	Yes	Highly optimal, production-standard
Bitwise Mask	(O(N))	(O(1))	No (English a-z only)	Advanced, demonstrates bitwise register arithmetic mastery