Backend interview prep

Start Learning

First Non Repeating Character

Java coding interview problem for Character Problems: First Non Repeating Character.

Finding the First Non-Repeating Character is one of the most frequently asked Java String interview questions.

Although the problem appears simple, it evaluates several important programming concepts, including:

  • String Traversal
  • Character Frequency
  • HashMap
  • LinkedHashMap
  • Arrays
  • Time Complexity
  • Space Complexity

Interviewers often ask several follow-up questions such as:

  • Can you solve it in one pass?
  • Can you preserve the insertion order?
  • Can you solve it without using collections?
  • How would you solve it for Unicode characters?
  • What if the input is a stream of characters?

Learning multiple approaches prepares you for all these interview variations.

Problem Statement

Given a string, find the first character that appears exactly once.

If no such character exists, return a special value such as:

'\0'

or

-1

depending on the problem statement.

Example 1

Input

aabbcdde

Output

c

Example 2

Input

leetcode

Output

l

Example 3

Input

aabbcc

Output

No Non-Repeating Character

Example 4

Input

swiss

Output

w

What is a Non-Repeating Character?

A non-repeating character is a character that appears exactly once in the string.

Example

banana

Character Frequencies

b → 1

a → 3

n → 2

First non-repeating character

b

Another Example

swiss

Frequencies

s → 3

w → 1

i → 1

The answer is

w

because it appears before

i

Why is this Question Asked in Interviews?

This problem evaluates whether candidates understand:

  • HashMap
  • LinkedHashMap
  • Frequency Counting
  • Arrays
  • String Traversal
  • Time Complexity

It also introduces concepts used in:

  • Data Analytics
  • Streaming Data
  • Text Processing
  • Log Analysis

Real-World Applications

Finding unique elements has many practical applications.

Log Processing

Find the first unique log entry.

Data Cleaning

Identify unique records.

Text Analytics

Detect unique characters or symbols.

Search Engines

Analyze uncommon search terms.

Fraud Detection

Detect unique transaction identifiers.

Understanding Character Frequency

Consider

programming

Count every character.

p → 1

r → 2

o → 1

g → 2

a → 1

m → 2

i → 1

n → 1

Now traverse the string again.

The first character whose frequency equals

1

is

p

LinkedHashMap vs HashMap

This is a common interview follow-up.

HashMap

Stores key-value pairs.

Does not preserve insertion order.

Example

b

a

n

may be stored internally as

n

b

a

LinkedHashMap

Stores key-value pairs.

Preserves insertion order.

Example

Input

banana

Insertion Order

b

a

n

The order remains unchanged.

This makes it perfect for this problem.

Mathematical Concept

Input

swiss

Frequency Table

s → 3

w → 1

i → 1

Traverse again.

s

↓

3

Ignore.

w

↓

1

Answer

w

Visual Representation

Input

aabbcdde

Frequency

a → 2

b → 2

c → 1

d → 2

e → 1

Traversal

a

↓

Ignore

b

↓

Ignore

c

↓

Answer

Dry Run

Input

swiss

Step 1

Count

s → 3

w → 1

i → 1

Step 2

Traverse

s

↓

3

Ignore

w

↓

1

Return

w

Approach 1 — Using LinkedHashMap (Recommended)

This is the most common interview solution.

The idea is simple.

  • Count every character.
  • Preserve insertion order.
  • Return the first character with frequency one.

Why LinkedHashMap?

Unlike HashMap,

LinkedHashMap remembers the order in which keys are inserted.

Example

banana

Stored Order

b

a

n

The first key having frequency one is the answer.

Algorithm

  1. Create a LinkedHashMap.
  2. Count every character.
  3. Traverse the map.
  4. Return the first key whose frequency equals one.

Java Program

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

public class FirstNonRepeatingCharacter {

    public static char firstUnique(String text) {

        LinkedHashMap<Character, Integer> map =
                new LinkedHashMap<>();

        for (char ch : text.toCharArray()) {

            map.put(ch,
                    map.getOrDefault(ch, 0) + 1);

        }

        for (Map.Entry<Character, Integer> entry
                : map.entrySet()) {

            if (entry.getValue() == 1) {

                return entry.getKey();

            }

        }

        return '\0';

    }

    public static void main(String[] args) {

        System.out.println(
                firstUnique("swiss"));

        System.out.println(
                firstUnique("aabbcdde"));

        System.out.println(
                firstUnique("leetcode"));

    }

}

Output

w

c

l

Step-by-Step Code Explanation

Create the map.

LinkedHashMap<Character, Integer> map =
        new LinkedHashMap<>();

Count every character.

map.put(ch,
        map.getOrDefault(ch, 0) + 1);

Example

banana

Produces

b → 1

a → 3

n → 2

Traverse the map.

for (Map.Entry<Character, Integer> entry
        : map.entrySet())

Since LinkedHashMap preserves insertion order,

the first character having frequency

1

is returned.

If nothing is found

return '\0';

Dry Run of LinkedHashMap Approach

Input

aabbcdde
Character Frequency
a 2
b 2
c 1
d 2
e 1

Traversal

a

↓

Ignore

b

↓

Ignore

c

↓

Return

Answer

c

Advantages

  • Easy to understand.
  • Preserves insertion order automatically.
  • Linear time complexity.
  • Most common interview solution.
  • Excellent readability.

Drawbacks

  • Uses additional memory.
  • Depends on Java Collections Framework.

Approach 2 — Using Frequency Array

If the string contains only lowercase English letters (or ASCII characters),

an integer array is faster than a HashMap.

Algorithm

  1. Create a frequency array.
  2. Count every character.
  3. Traverse the original string.
  4. Return the first character whose frequency is one.

Java Program

public class FirstUniqueUsingArray {

    public static char firstUnique(String text) {

        int[] frequency = new int[256];

        for (char ch : text.toCharArray()) {

            frequency[ch]++;

        }

        for (char ch : text.toCharArray()) {

            if (frequency[ch] == 1) {

                return ch;

            }

        }

        return '\0';

    }

    public static void main(String[] args) {

        System.out.println(
                firstUnique("swiss"));

        System.out.println(
                firstUnique("leetcode"));

    }

}

Output

w

l

Step-by-Step Code Explanation

Create the array.

int[] frequency = new int[256];

Each index represents one ASCII character.

Count frequencies.

frequency[ch]++;

Traverse the string again.

if (frequency[ch] == 1)

Return the first unique character.

Time & Space Complexity

Approach Time Extra Space
LinkedHashMap O(n) O(k)
Frequency Array O(n) O(1)*

Where:

  • n = length of the string
  • k = number of distinct characters

*For a fixed ASCII character set, the array size is constant (256), so the extra space is treated as O(1).

Comparison of Approaches

Feature LinkedHashMap Frequency Array
Interview Friendly ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐
Easy to Understand ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐
Performance ⭐⭐⭐⭐ ⭐⭐⭐⭐⭐
Supports Unicode ⭐⭐⭐⭐⭐ Limited (ASCII example)

Advantages

  • Both approaches run in O(n) time.
  • LinkedHashMap naturally preserves insertion order.
  • Frequency Array is faster for fixed-size character sets such as ASCII.
  • Both are widely accepted interview solutions.

Drawbacks

  • LinkedHashMap uses additional memory for map entries.
  • Frequency Array is not suitable for arbitrary Unicode character sets without modifications.
  • Both require two passes over the input.

In Part 2, we'll cover:

  • Approach 3 – Using HashMap with Two Passes
  • Approach 4 – Using Java Streams
  • Approach 5 – Using Queue + HashMap (Streaming Characters)
  • Unicode Considerations
  • Comparison of All Approaches
  • Common Interview Mistakes
  • Edge Cases
  • Interview Follow-up Questions
  • Related Problems
  • Key Takeaways
  • Frequently Asked Interview Questions
  • Interview Tips

Approach 3 — Using HashMap with Two Passes

Another popular interview solution uses a HashMap.

Unlike LinkedHashMap, a HashMap does not preserve insertion order.

Therefore, after counting the characters, we traverse the original string again to find the first character whose frequency is one.

Why Does This Work?

Example

banana

Frequency Map

b → 1

a → 3

n → 2

Traverse the original string.

b

↓

1

Answer

b

The second traversal preserves the original order.

Algorithm

  1. Create a HashMap.
  2. Count every character.
  3. Traverse the original string.
  4. Return the first character having frequency one.

Java Program

import java.util.HashMap;
import java.util.Map;

public class FirstUniqueHashMap {

    public static char firstUnique(String text) {

        Map<Character, Integer> map =
                new HashMap<>();

        for (char ch : text.toCharArray()) {

            map.put(ch,
                    map.getOrDefault(ch, 0) + 1);

        }

        for (char ch : text.toCharArray()) {

            if (map.get(ch) == 1) {

                return ch;

            }

        }

        return '\0';

    }

    public static void main(String[] args) {

        System.out.println(
                firstUnique("swiss"));

        System.out.println(
                firstUnique("banana"));

    }

}

Output

w

b

Advantages

  • Simple implementation.
  • Works for any character set supported by Java.
  • Frequently asked in interviews.

Drawbacks

  • Requires two passes.
  • Does not preserve insertion order internally.

Approach 4 — Using Java Streams

Java 8 Streams provide a functional programming approach.

Although this solution is concise,

it is generally less efficient than loops.

Algorithm

  1. Convert characters into a stream.
  2. Group by character.
  3. Count frequencies.
  4. Return the first character with count one.

Java Program

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

public class FirstUniqueStreams {

    public static Character firstUnique(String text) {

        Map<Character, Long> frequency =
                text.chars()
                        .mapToObj(ch -> (char) ch)
                        .collect(Collectors.groupingBy(
                                Function.identity(),
                                LinkedHashMap::new,
                                Collectors.counting()));

        return frequency.entrySet()
                .stream()
                .filter(entry -> entry.getValue() == 1)
                .map(Map.Entry::getKey)
                .findFirst()
                .orElse(null);

    }

    public static void main(String[] args) {

        System.out.println(
                firstUnique("swiss"));

    }

}

Output

w

Advantages

  • Modern Java style.
  • Concise implementation.
  • Good demonstration of Java Streams.

Drawbacks

  • More overhead than loops.
  • Harder for beginners.
  • Usually not preferred in performance-critical interviews.

Approach 5 — Using Queue + HashMap (Streaming Characters)

Suppose characters arrive continuously.

Example

a

↓

ab

↓

abc

↓

abca

↓

abcab

We must always know the current first non-repeating character.

A Queue solves this efficiently.

Idea

Maintain

  • Queue → insertion order
  • HashMap → frequencies

Whenever a character repeats,

remove it from the front until the queue contains only unique characters.

Visualization

Input Stream

a

b

a

c

d

Queue

a

↓

a b

↓

b

↓

b c

↓

b c d

Current Answer

b

Algorithm

  1. Count frequencies.
  2. Insert new characters into the queue.
  3. Remove repeated characters from the front.
  4. Front of the queue is always the answer.

Java Program

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class FirstUniqueStreaming {

    public static void firstUnique(String text) {

        Map<Character, Integer> map =
                new HashMap<>();

        Queue<Character> queue =
                new LinkedList<>();

        for (char ch : text.toCharArray()) {

            map.put(ch,
                    map.getOrDefault(ch, 0) + 1);

            queue.offer(ch);

            while (!queue.isEmpty()
                    && map.get(queue.peek()) > 1) {

                queue.poll();

            }

        }

        if (queue.isEmpty()) {

            System.out.println(
                    "No Unique Character");

        } else {

            System.out.println(queue.peek());

        }

    }

    public static void main(String[] args) {

        firstUnique("swiss");

    }

}

Output

w

Advantages

  • Excellent for streaming data.
  • Frequently asked in advanced interviews.
  • Constant-time queue operations.

Drawbacks

  • Slightly more complex.
  • Uses two data structures.

Unicode Considerations

Java strings support Unicode.

Examples

こんにちは

नमस्ते

😊😊😂

The HashMap and LinkedHashMap approaches work well for general Java strings.

If your application must correctly handle supplementary Unicode characters (such as many emoji), iterate over Unicode code points instead of individual char values.

Edge Cases

Input Expected Output
"" No Character
"a" a
"aaaa" No Character
"abcd" a
"aabbccd" d
null Handle appropriately based on application requirements

Time & Space Complexity

Approach Time Extra Space
LinkedHashMap O(n) O(k)
Frequency Array O(n) O(1)*
HashMap + Two Passes O(n) O(k)
Java Streams O(n) O(k)
Queue + HashMap O(n) O(k)

Where:

  • n = length of the string
  • k = number of distinct characters

*For a fixed ASCII character set, the array size is constant.

Comparison of All Approaches

Approach Interview Friendly Performance Best Use Case
LinkedHashMap ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ General interviews
Frequency Array ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ ASCII-only strings
HashMap + Two Passes ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ General-purpose solution
Java Streams ⭐⭐⭐⭐ ⭐⭐⭐ Modern Java code
Queue + HashMap ⭐⭐⭐⭐⭐ ⭐⭐⭐⭐⭐ Streaming characters

Common Interview Mistakes

Mistake 1

Returning the first unique key from a HashMap.

Wrong

map.entrySet().iterator().next()

A HashMap does not preserve insertion order.

Mistake 2

Using only one traversal.

You must first know the frequency of every character before determining the first unique one (unless solving the streaming variation).

Mistake 3

Confusing unique with distinct.

Example

banana

Unique

b

Distinct characters

b

a

n

These are different concepts.

Mistake 4

Ignoring empty strings.

Always handle

""

gracefully.

Mistake 5

Using an ASCII frequency array for Unicode input.

Use a HashMap (or Unicode code points) when the character set is not fixed.

Interview Follow-up Questions

Q1. Why is LinkedHashMap preferred over HashMap?

Q2. Can you solve this in one pass?

Q3. How would you solve it for a stream of characters?

Q4. How would you support Unicode?

Q5. What is the time complexity?

Q6. Can you solve it without collections?

Q7. Which solution is best for ASCII input?

Q8. Why does a Queue help in streaming scenarios?

Q9. How would you process millions of characters?

Q10. What if the input is case-insensitive?

Related Problems

  • First Repeating Character
  • Count Character Frequency
  • Remove Duplicate Characters
  • String Compression
  • Valid Anagram
  • Longest Substring Without Repeating Characters
  • Group Anagrams
  • Find All Duplicates

Key Takeaways

  • The First Non-Repeating Character is the first character whose frequency is exactly one.
  • LinkedHashMap is the most common interview solution because it preserves insertion order.
  • A Frequency Array is the fastest approach for fixed-size character sets such as ASCII.
  • A HashMap with Two Passes is a simple and widely accepted solution.
  • Java Streams provide a concise functional implementation but are generally less efficient than loops.
  • A Queue + HashMap is the preferred approach when characters arrive as a stream.

Frequently Asked Interview Questions

Q1. Which solution is best for interviews?

The LinkedHashMap approach is usually the best choice because it is easy to explain, preserves insertion order, and runs in O(n) time.

Q2. Why not use a HashMap alone?

A HashMap does not preserve insertion order.

Therefore, either:

  • Traverse the original string again, or
  • Use a LinkedHashMap.

Q3. Which approach is fastest?

For ASCII input,

the Frequency Array approach is typically the fastest because array indexing is constant time.

Q4. Which approach works for streaming input?

The Queue + HashMap solution efficiently maintains the current first non-repeating character as new characters arrive.

Q5. Can this problem be solved in one pass?

For a fixed input string, most standard solutions require two logical steps: counting frequencies and identifying the first unique character.

For streaming input, the Queue + HashMap approach updates the answer incrementally as characters arrive.

Interview Tip

If an interviewer asks:

"Find the first non-repeating character in a string."

Start with the LinkedHashMap solution because it is the industry-standard interview answer.

Then discuss alternative approaches:

  1. LinkedHashMap (recommended)
  2. Frequency Array (ASCII optimization)
  3. HashMap + Two Passes
  4. Java Streams
  5. Queue + HashMap (streaming data)

Before coding, clarify requirements such as:

  • Can the input contain Unicode characters?
  • Should uppercase and lowercase characters be treated differently?
  • What should be returned if no unique character exists?
  • Is the input a complete string or a stream of incoming characters?

Answering these questions first demonstrates strong problem-solving and communication skills in Java interviews.