Unique characters in an ASCII string

You're sitting in an IBM screening interview, and the interviewer opens with something deceptively simple: "Given a string of ASCII characters, can you tell me if every character in it is unique?" It's the kind of question that separates candidates who rush to a brute-force nested loop from those who reach for the right data structure immediately. This problem, also known as "Is Unique" from Cracking the Coding Interview, is a staple warm-up that tests your grasp of sets, character encodings, and the ability to recognize constant-space constraints hiding in plain sight.

TL;DR

Iterate through the string one character at a time, adding each character to a HashSet. Before adding, check if the set already contains that character. If it does, return false immediately. If you make it through the entire string without finding a duplicate, return true. This runs in O(n) time, and since the ASCII character set is fixed at 128 values, the set never grows beyond a constant size, giving O(1) space.

Prefer a different language? Jump to solutions in other languages.

Why This Problem Matters

This is often the very first question in a coding interview, and for good reason. It tests three things at once: whether you know when to use a set versus a list or map, whether you understand character encoding constraints, and whether you can reason about edge cases like empty strings. Get this right quickly and you set the tone for the rest of the interview. Stumble here and you're playing catch-up.

ASCII: A Quick Refresher

Before we dig into the algorithm, let's clarify what "ASCII string" means in this context. ASCII (American Standard Code for Information Interchange) defines 128 characters, each mapped to an integer from 0 to 127. This includes uppercase and lowercase letters, digits, punctuation, and control characters.

The key insight for this problem: there are only 128 possible ASCII characters. That ceiling matters for both our algorithm's correctness and its space analysis. If a string has more than 128 characters, it must contain a duplicate by the pigeonhole principle.

Understanding the Problem

Given: A string containing only standard ASCII characters (codes 0-127) Task: Determine if every character in the string appears exactly once Return: true if all characters are unique, false if any character repeats

Here are the examples from the problem:

areAllAsciiCharactersUnique("abcde") -> true
areAllAsciiCharactersUnique("madam") -> false
areAllAsciiCharactersUnique("")      -> true

Edge Cases

1. Empty string: No characters means no duplicates, so return true
2. Single character: Always unique, return true
3. String longer than 128 characters: Must contain a duplicate (pigeonhole principle)
4. Strings with spaces and special characters: "4 0 3" has spaces that count as characters

Solution Approach

The brute-force way would be to compare every character against every other character, giving O(n^2) time. But we can do much better by trading a small amount of space for a huge speedup.

The idea is straightforward: as you walk through the string, keep a record of every character you've already seen. For each new character, check if it's in your record. If it is, you found a duplicate. If not, add it and move on.

A HashSet is the perfect data structure here. It gives O(1) average time for both contains and add operations, which keeps our overall time linear.

Tracing Through "abcde"

Let's watch the set grow as we process a string with all unique characters:

Every character passes the uniqueness check, so we reach the end and return true.

Tracing Through "madam"

Now let's see what happens with a string that has duplicates:

At the fourth character 'a', the set already contains it. We return false immediately without processing the rest of the string. This early exit is one of the nice properties of this approach.

Implementation

Here's the Java solution:

import java.util.HashSet;
import java.util.Set;

public class Solution {
  public boolean areAllAsciiCharactersUnique(String str) {
    // Initialize a HashSet to store seen characters
    Set<Character> seenSet = new HashSet<>();

    // Convert the string to a character array and loop over it
    for (char c : str.toCharArray()) {
      // If the character is already in the set, we found a duplicate
      if (seenSet.contains(c)) {
        return false;
      }
      // Otherwise, add it to the set
      seenSet.add(c);
    }

    // No duplicates found
    return true;
  }
}

The logic maps directly to our trace above. Three lines do all the work: check, return early, or add. Everything else is scaffolding.

Complexity Analysis

Time Complexity: O(n)

We iterate through each character once, performing O(1) set operations at each step. In the worst case (all unique), we process all n characters. In the best case (early duplicate), we stop after just a few characters.

There's a subtlety worth mentioning: since the string is limited to ASCII, the loop never runs more than 128 times. Technically this makes the time O(min(n, 128)), which is O(1) in the strict sense. But saying O(n) is standard practice for this type of problem and is what interviewers expect to hear.

Space Complexity: O(1)

The HashSet holds at most 128 entries (one per ASCII character), regardless of the string length. Since 128 is a fixed constant, the space is O(1). This is a case where the constant bound on the input alphabet gives us constant space for free.

Alternative Approaches

*In-place sort achieves O(1) extra space but mutates the original string.

Common Pitfalls

1. Forgetting the empty string: An empty string has no duplicates. Don't add a special check that accidentally returns false for empty input.

2. Using a List instead of a Set: Calling list.contains() is O(n) per lookup, turning the overall algorithm into O(n^2). Always reach for a HashSet when you need fast membership testing.

3. Ignoring the ASCII constraint: If you don't mention the 128-character bound, you're missing the space analysis. Interviewers want to hear that the space is technically O(1) because of the fixed alphabet size.

4. Not considering the pigeonhole principle: For bonus points, you can add an early check: if the string length exceeds 128, return false immediately. This shows you understand the mathematical foundation behind the problem.

Interview Tips

When this comes up in an interview:

1. Clarify the character set first. "Is the input limited to ASCII, or could it be Unicode?" This changes the space analysis entirely. For Unicode, the set could grow much larger.

2. Mention multiple approaches. Start with the HashSet solution, then briefly mention the bit vector approach for lowercase-only strings and the sort-then-scan approach. This shows breadth of knowledge.

3. Talk about the pigeonhole shortcut. If the string is longer than the character set size, you can return false before processing anything. Interviewers love seeing this kind of mathematical reasoning.

4. If you get a follow-up: "Can you do it without extra data structures?" That's a nudge toward sorting the string in-place or using a bit vector.

Key Takeaways

• A HashSet gives O(1) lookup and insertion, making it the ideal choice for tracking seen elements during a single pass through a sequence.
• When the input alphabet is fixed (128 ASCII characters), any data structure bounded by that alphabet size uses O(1) space, even though it grows with input.
• The pigeonhole principle provides a powerful early exit: if the input length exceeds the alphabet size, duplicates are guaranteed.
• Early termination on the first duplicate makes this approach efficient on average, not just in the worst case.
• This "seen set" pattern recurs throughout string and array problems. Master it here and you'll recognize it in problems like finding the first non-repeating character, longest substring without repeats, and anagram detection.

Practice and Related Problems

Once you're comfortable with this approach, these related problems will reinforce the same patterns:

• Find the Unique Number - uses a set to find the element that appears only once
• Palindrome Tester - another string traversal with character-level checks
• Longest Substring Without Repeated Characters - extends the "seen set" idea with a sliding window

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. Whether you're just getting started or sharpening your skills for a FAANG loop, building fluency with these fundamentals pays off quickly.

Solutions in Other Languages

Python

class Solution:
    def are_all_ascii_characters_unique(self, string):
        seen_set = set()

        for char in string:
            if char in seen_set:
                return False
            seen_set.add(char)

        return True

JavaScript

class Solution {
  areAllAsciiCharactersUnique(str) {
    const seenSet = new Set();

    for (let char of str) {
      if (seenSet.has(char)) {
        return false;
      }
      seenSet.add(char);
    }

    return true;
  }
}

TypeScript

class Solution {
  areAllAsciiCharactersUnique(str: string): boolean {
    const seenSet = new Set<string>();

    for (const c of str) {
      if (seenSet.has(c)) {
        return false;
      }
      seenSet.add(c);
    }

    return true;
  }
}

C++

#include <set>
#include <string>

class Solution {
public:
  bool areAllAsciiCharactersUnique(std::string str) {
    std::set<char> seenSet;

    for (auto &c : str) {
      if (seenSet.find(c) != seenSet.end()) {
        return false;
      }
      seenSet.insert(c);
    }

    return true;
  }
};

Go

func (s *Solution) AreAllAsciiCharactersUnique(str string) bool {
    set := make(map[int32]bool)

    for _, c := range str {
        if set[c] {
            return false
        }
        set[c] = true
    }

    return true
}

Scala

class Solution {
  def areAllAsciiCharactersUnique(str: String): Boolean = {
    import scala.collection.mutable

    val seenSet: mutable.Set[Char] = mutable.Set()

    str.toCharArray.foreach { character: Char =>
      if (seenSet.contains(character)) {
        return false
      }
      seenSet.add(character)
    }

    true
  }
}

Kotlin

class Solution {
    fun areAllAsciiCharactersUnique(str: String): Boolean {
        val seenSet = mutableSetOf<Char>()

        for (c in str) {
            if (c in seenSet) {
                return false
            }
            seenSet.add(c)
        }

        return true
    }
}

Swift

class Solution {
    func areAllAsciiCharactersUnique(_ str: String) -> Bool {
        var seenSet = Set<Character>()

        for c in str {
            if seenSet.contains(c) {
                return false
            }
            seenSet.insert(c)
        }

        return true
    }
}

Rust

use std::collections::HashSet;

impl Solution {
    pub fn are_all_ascii_characters_unique(&self, s: String) -> bool {
        let mut seen_set: HashSet<char> = HashSet::new();

        for c in s.chars() {
            if seen_set.contains(&c) {
                return false;
            }
            seen_set.insert(c);
        }

        true
    }
}

Ruby

require 'set'

class Solution
  def are_all_ascii_characters_unique(str)
    seen_set = Set.new

    str.each_char do |c|
      return false if seen_set.include?(c)
      seen_set.add(c)
    end

    true
  end
end

C#

public class Solution {
    public bool areAllAsciiCharactersUnique(string str) {
        var seenSet = new HashSet<char>();

        foreach (char c in str) {
            if (seenSet.Contains(c)) {
                return false;
            }
            seenSet.Add(c);
        }

        return true;
    }
}

Dart

class Solution {
  bool areAllAsciiCharactersUnique(String str) {
    Set<String> seenSet = {};

    for (String c in str.split('')) {
      if (seenSet.contains(c)) {
        return false;
      }
      seenSet.add(c);
    }

    return true;
  }
}

PHP

class Solution {
    public function areAllAsciiCharactersUnique(string $str): bool {
        $seenSet = [];

        foreach (str_split($str) as $char) {
            if (isset($seenSet[$char])) {
                return false;
            }
            $seenSet[$char] = true;
        }

        return true;
    }
}