Find the first non-duplicate character in a string

You're sitting across from a Bloomberg engineer who slides a laptop toward you. "Given a string," they say, "find the first character that doesn't repeat anywhere else in it." You nod, recognizing this as a classic warm-up that tests your understanding of hash maps and insertion order. This problem, also known as "First Unique Character in a String" on other platforms, is a staple at companies like Cisco and Bloomberg because it reveals how well a candidate thinks about data structure selection.

TL;DR

Build a frequency map that preserves insertion order (like Java's LinkedHashMap), count each character in a single pass, then iterate through the map and return the first character with a count of 1. This runs in O(n) time and O(n) space. The critical insight is choosing a data structure that maintains the order characters were first seen, so your second pass finds the answer immediately.

Why This Problem Matters

Finding the first unique character tests two skills simultaneously: counting frequencies and respecting order. On its own, either task is trivial. But combining them forces you to think about which data structure gives you both. It's the kind of problem that separates candidates who memorize solutions from those who reason about tradeoffs, and it sets the stage for harder string problems like finding the longest substring without repeating characters.

Understanding the Problem

Let's pin down what we need:

Given: A string of characters Find: The first character that appears exactly once Constraint: The string always contains at least one unique character Goal: O(n) time, O(n) space

Here's the first example. The string is "abcdcd", and we need to find the first character that doesn't repeat:

Characters c and d each appear twice, while a and b each appear once. Since a comes first, the answer is 'a'.

Now consider "aabcdc":

Here a appears twice and c appears twice. Both b and d appear once, but b comes first. The answer is 'b'.

Edge Cases to Consider

1. Single character: "b" has only one character, so it's the answer
2. All unique: "abcdef" returns 'a' since every character is unique
3. Duplicates at the end: "aabbccd" returns 'd', the only unique character

Solution Approach

The naive approach would check every character against every other character, giving O(n^2) time. We can do much better.

Why a Regular HashMap Falls Short

A standard HashMap gives O(1) lookups and updates, which handles the counting step perfectly. But when you iterate over a HashMap, the order is unpredictable. You'd need to loop through the original string again to check each character's count in order.

That works, but there's a cleaner way.

The LinkedHashMap Advantage

Java's LinkedHashMap combines a hash table with a doubly linked list that tracks insertion order. When you iterate over it, entries come back in the order they were first inserted. This means after building the frequency map, your very first entry with count 1 is the answer.

Here's the two-pass strategy:

Pass 1 - Build the frequency map: Walk through the string character by character, updating each character's count.

Pass 2 - Find the first unique: Iterate through the map in insertion order. The first entry with a value of 1 is our answer.

For the string "abcdcd", a is the first map entry with count 1, so we return 'a'.

Let's verify with "aabcdc":

Here a has count 2, so we skip it. b has count 1, so we return 'b'.

Implementation

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

import java.util.LinkedHashMap;
import java.util.Map;

public class Solution {
  public char firstUniqueChar(String str) {
    // Build frequency map preserving insertion order
    Map<Character, Integer> charCounts = new LinkedHashMap<>();

    for (char c : str.toCharArray()) {
      charCounts.put(c, charCounts.getOrDefault(c, 0) + 1);
    }

    // Return first character with count of 1
    for (Map.Entry<Character, Integer> entry : charCounts.entrySet()) {
      if (entry.getValue() == 1) {
        return entry.getKey();
      }
    }

    // Per constraints, this line is never reached
    return '\0';
  }
}

Let's trace through with "abcdcd":

Pass 1 builds: {a:1, b:1, c:2, d:2}

• a goes in with count 1
• b goes in with count 1
• c goes in with count 1
• d goes in with count 1
• c updates to count 2
• d updates to count 2

Pass 2 scans the map in insertion order:

• a has count 1. Return 'a'.

Done in two linear passes.

Alternative: Array-Based Approach

If you know the input is limited to ASCII characters, you can skip the hash map entirely:

public char firstUniqueChar(String str) {
    int[] counts = new int[256];

    for (char c : str.toCharArray()) {
        counts[c]++;
    }

    for (char c : str.toCharArray()) {
        if (counts[c] == 1) {
            return c;
        }
    }

    return '\0';
}

This uses a fixed-size array as a frequency table. The second pass walks the original string (not the array) to preserve character order. It's slightly faster in practice due to better cache locality, and the space is O(1) since the array size is constant.

In an interview, mention both approaches. The LinkedHashMap version demonstrates your knowledge of Java's collections framework, while the array version shows you can optimize when the character set is bounded.

Complexity Analysis

Time Complexity: O(n)

Two passes through the input, each doing O(1) work per character. Map operations (put, getOrDefault) are O(1) amortized, and iterating the map is O(n) total.

Space Complexity: O(n)

The frequency map stores at most one entry per distinct character. In the worst case (all unique characters), this equals the string length. For ASCII-only strings, the space is bounded at O(1) since there are at most 256 possible keys.

Common Pitfalls

1. Using a regular HashMap then iterating it: The iteration order is undefined, so you might return a unique character that isn't the first one.

2. Scanning the map instead of the string in the array approach: If you iterate through indices 0-255 of a frequency array, you'll find a unique character, but it will be the one with the lowest ASCII value, not the first one in the string.

3. Forgetting getOrDefault: Without it, you'll get a NullPointerException when calling arithmetic operations on a null Integer:

   // Wrong - throws NPE on first occurrence
   charCounts.put(c, charCounts.get(c) + 1);
   
   // Correct
   charCounts.put(c, charCounts.getOrDefault(c, 0) + 1);
   

4. Returning the wrong type: In Java, LinkedHashMap entries return boxed Character objects. The method signature expects a primitive char, but auto-unboxing handles this. Just be aware of it if null values are possible.

Interview Tips

When solving this in an interview:

1. Start by clarifying: "Can the string contain Unicode, or just ASCII?" This determines whether the array optimization is valid and shows you think about edge cases.

2. Mention the tradeoff: "I can use a LinkedHashMap to preserve insertion order, or iterate the string twice with a regular map. Both are O(n), but LinkedHashMap makes the code cleaner."

3. Draw the frequency map: Sketch out {a:1, b:1, c:2, d:2} for the example input. Interviewers want to see that you understand the data structure's state.

4. Know your follow-ups: Be ready for "What if the string is a character stream?" or "What if you need the index, not the character?"

Solutions in Other Languages

Python

class Solution:
    def first_unique_char(self, string: str) -> str:
        char_counts = {}

        for c in string:
            char_counts[c] = char_counts.get(c, 0) + 1

        for c in string:
            if char_counts[c] == 1:
                return c

        return ""

Python dictionaries maintain insertion order as of Python 3.7, so this follows the same logic. The second pass iterates the string rather than the dictionary, which works identically here since we're checking order of appearance.

JavaScript

class Solution {
  firstUniqueChar(str) {
    const charCounts = new Map();

    for (const c of str) {
      charCounts.set(c, (charCounts.get(c) || 0) + 1);
    }

    for (const c of str) {
      if (charCounts.get(c) === 1) {
        return c;
      }
    }

    return "";
  }
}

JavaScript's Map preserves insertion order by spec. The || 0 pattern provides a default when the key hasn't been seen yet.

TypeScript

class Solution {
  firstUniqueChar(str: string): string {
    const charCounts = new Map<string, number>();

    for (const c of str) {
      charCounts.set(c, (charCounts.get(c) || 0) + 1);
    }

    for (const c of str) {
      if (charCounts.get(c) === 1) {
        return c;
      }
    }

    return "";
  }
}

Same approach as JavaScript with explicit type annotations on the Map.

C++

#include <unordered_map>
#include <string>

class Solution {
public:
  char firstUniqueChar(const std::string &str) {
    std::unordered_map<char, int> charCounts;

    for (auto c : str) {
      charCounts[c]++;
    }

    for (auto c : str) {
      if (charCounts[c] == 1) {
        return c;
      }
    }

    return '\0';
  }
};

C++'s unordered_map doesn't preserve insertion order, so the second pass iterates the string to maintain character order. The [] operator default-initializes int to 0, making the increment clean.

Go

func (s *Solution) FirstUniqueChar(str string) rune {
    charCounts := map[rune]int{}

    for _, c := range str {
        charCounts[c]++
    }

    for _, c := range str {
        if charCounts[c] == 1 {
            return c
        }
    }

    return 0
}

Go maps don't preserve order, so we iterate the string on the second pass. Using map[rune]int ensures proper Unicode support since range over a string yields runes. The zero value for int is 0, so charCounts[c]++ works without initialization.

Scala

import scala.collection.mutable

class Solution {
  def firstUniqueChar(str: String): Char = {
    val charCounts = mutable.LinkedHashMap[Char, Int]()

    str.foreach { c =>
      charCounts.put(c, charCounts.getOrElse(c, 0) + 1)
    }

    str.find { c =>
      charCounts(c) == 1
    }.get
  }
}

Scala's mutable.LinkedHashMap preserves insertion order like Java's. The find method returns the first character matching the predicate, wrapped in an Option.

Kotlin

class Solution {
    fun firstUniqueChar(str: String): Char {
        val charCounts = linkedMapOf<Char, Int>()

        for (c in str) {
            charCounts[c] = charCounts.getOrDefault(c, 0) + 1
        }

        for ((char, count) in charCounts) {
            if (count == 1) {
                return char
            }
        }

        return '\u0000'
    }
}

Kotlin's linkedMapOf creates a LinkedHashMap under the hood. Destructuring in the for loop makes the second pass readable.

Ruby

class Solution
  def first_unique_char(str)
    char_counts = {}

    str.chars.each do |c|
      char_counts[c] = char_counts.fetch(c, 0) + 1
    end

    result = char_counts.find { |_, count| count == 1 }
    result&.first
  end
end

Ruby hashes maintain insertion order since Ruby 1.9. The fetch method with a default value avoids nil arithmetic, and find returns the first key-value pair matching the block.

Rust

use std::collections::HashMap;

impl Solution {
    pub fn first_unique_char(&self, s: String) -> char {
        let mut char_counts: HashMap<char, i32> = HashMap::new();

        for c in s.chars() {
            *char_counts.entry(c).or_insert(0) += 1;
        }

        for c in s.chars() {
            if char_counts[&c] == 1 {
                return c;
            }
        }

        '\0'
    }
}

Rust's entry API elegantly handles the "insert if absent, update if present" pattern. The second pass iterates the string since HashMap doesn't guarantee order.

Swift

class Solution {
    func firstUniqueChar(_ str: String) -> Character {
        var charCounts: [Character: Int] = [:]

        for c in str {
            charCounts[c, default: 0] += 1
        }

        for c in str {
            if charCounts[c] == 1 {
                return c
            }
        }

        return "\0"
    }
}

Swift's dictionary subscript with default is similar to Java's getOrDefault. Since Swift dictionaries don't preserve order, the second pass iterates the string.

Dart

class Solution {
  String firstUniqueChar(String str) {
    Map<String, int> charCounts = {};

    for (String c in str.split('')) {
      charCounts[c] = (charCounts[c] ?? 0) + 1;
    }

    for (var entry in charCounts.entries) {
      if (entry.value == 1) {
        return entry.key;
      }
    }

    return '';
  }
}

Dart's Map preserves insertion order by default. The null-aware ?? operator provides the default value for unseen characters.

C#

public class Solution {
    public char FirstUniqueChar(string str) {
        var charCounts = new Dictionary<char, int>();

        foreach (char c in str) {
            charCounts[c] = charCounts.GetValueOrDefault(c, 0) + 1;
        }

        foreach (char c in str) {
            if (charCounts[c] == 1) {
                return c;
            }
        }

        return '\0';
    }
}

C#'s Dictionary does not guarantee insertion order, so the second pass iterates the original string to find the first unique character in order. GetValueOrDefault works like Java's getOrDefault.

PHP

class Solution {
    public function firstUniqueChar(string $str): string {
        $charCounts = [];

        foreach (str_split($str) as $char) {
            $charCounts[$char] = ($charCounts[$char] ?? 0) + 1;
        }

        foreach (str_split($str) as $char) {
            if ($charCounts[$char] === 1) {
                return $char;
            }
        }

        return '';
    }
}

PHP arrays preserve insertion order. The null coalescing operator ?? handles missing keys cleanly.

Key Takeaways

• The two-pass frequency map pattern solves this in O(n) time: first pass counts, second pass finds the first count of 1.
• Data structure selection matters. A LinkedHashMap (Java/Scala/Kotlin) lets you iterate in insertion order, while languages without ordered maps (C++, Go, Rust) require iterating the original string on the second pass.
• For ASCII-only inputs, a fixed-size int[256] array is faster and uses O(1) space. Mention this optimization in interviews to show practical awareness.
• Watch out for NullPointerException in Java when using get() instead of getOrDefault() on the first occurrence of a character.
• This frequency-counting pattern is a building block for harder problems like finding the longest substring without repeating characters or grouping anagrams.

Practice Makes Perfect

Once you're comfortable with this problem, try these related challenges to build on the same frequency-counting pattern:

• Find duplicate numbers in an array
• Anagram checker
• Longest substring without repeated characters
• Group anagrams

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 tech companies. Whether you're just getting started or preparing for a FAANG interview, building fluency with patterns like frequency maps will pay off in every round.