First Non Repeating Character Using Hash in DSA Java

Mental Model

We want to find the first letter in a word that appears only once by counting how many times each letter shows up.

Analogy: Imagine a classroom where each student raises their hand once. We want to find the first student who raised their hand only once, ignoring those who raised it multiple times.

word: [a] -> [b] -> [c] -> [a] -> [b] -> [d]
count: {a:2, b:2, c:1, d:1}
↑ first unique is 'c'

Dry Run Walkthrough

Input: string: "swiss"

Goal: Find the first character that appears only once in the string

Step 1: Count frequency of 's'

counts = {s:1}

Why: Start counting characters to know how many times each appears

Step 2: Count frequency of 'w'

counts = {s:1, w:1}

Why: Add next character count

Step 3: Count frequency of 'i'

counts = {s:1, w:1, i:1}

Why: Add next character count

Step 4: Count frequency of 's' again

counts = {s:2, w:1, i:1}

Why: Increase count for repeated character

Step 5: Count frequency of 's' again

counts = {s:3, w:1, i:1}

Why: Increase count for repeated character

Step 6: Scan string from start to find first char with count 1

Check 's' (count 3), 'w' (count 1) -> first unique is 'w'

Why: Find first character that appears only once

Result:

Final counts: {s:3, w:1, i:1}
First non repeating character: w

Annotated Code

DSA Java

import java.util.HashMap;

public class FirstNonRepeatingChar {

    public static char firstNonRepeating(String s) {
        HashMap<Character, Integer> counts = new HashMap<>();
        // Count frequency of each character
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }
        // Find first character with count 1
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (counts.get(c) == 1) {
                return c;
            }
        }
        return '_'; // return underscore if no unique char found
    }

    public static void main(String[] args) {
        String input = "swiss";
        char result = firstNonRepeating(input);
        System.out.println("First non repeating character: " + result);
    }
}

counts.put(c, counts.getOrDefault(c, 0) + 1);

increment count for character c or add it if not present

if (counts.get(c) == 1) {

check if current character count is exactly one

return c;

return the first character found with count one

Output

First non repeating character: w

Complexity Analysis

Time: O(n) because we scan the string twice: once to count and once to find the first unique character

Space: O(k) where k is the number of unique characters, because we store counts in a hash map

vs Alternative: Compared to checking each character by scanning the whole string repeatedly (O(n^2)), this hash map method is much faster and efficient

Edge Cases

empty string

returns '_' indicating no unique character

DSA Java

return '_' // return underscore if no unique char found

all characters repeating

returns '_' indicating no unique character

DSA Java

return '_' // return underscore if no unique char found

string with one character

returns that character as it is unique

DSA Java

if (counts.get(c) == 1) { return c; }

When to Use This Pattern

When you need to find the first unique element in a sequence, use a hash map to count frequencies and then scan to find the first with count one for efficient lookup.

Common Mistakes

Mistake: Checking uniqueness by scanning the whole string for each character causing O(n^2) time
Fix: Use a hash map to count all characters first, then scan once to find the first unique

Summary

Finds the first character in a string that appears only once using a hash map to count frequencies.

Use when you need to quickly identify the first unique element in a sequence.

Count all characters first, then scan once to find the first with count one.

Practice

1. What does the "First Non Repeating Character Using Hash" algorithm primarily do?

easy

A. Reverses the string using a hash map

B. Counts the total number of characters in a string

C. Sorts characters of a string in alphabetical order

D. Finds the first character in a string that appears only once

Solution

1. Step 1: Understand the problem goal

   The algorithm aims to find the first character in the string that does not repeat anywhere else.

2. Step 2: Role of hash map

   A hash map stores character counts to quickly check which characters appear once.

3. Final Answer:

   Finds the first character in a string that appears only once -> Option D

4. Quick Check:

   First non repeating character = Finds the first character in a string that appears only once [OK]

Hint: Look for the first unique character using counts [OK]

Common Mistakes:

• Thinking it counts total characters only
• Confusing sorting with finding unique character
• Assuming it reverses the string

2. Which Java collection is best suited to store character counts for this problem?

easy

A. ArrayList<Character>

B. HashMap

C. LinkedList<Character>

D. TreeSet<Character>

Solution

1. Step 1: Identify data structure needs

   We need to map each character to its count, so a key-value structure is required.

2. Step 2: Choose appropriate Java collection

   HashMap stores characters as keys and their counts as values efficiently.

3. Final Answer:

   HashMap -> Option B

4. Quick Check:

   Use HashMap for character counts [OK]

Hint: Use HashMap for key-value pairs of char and count [OK]

Common Mistakes:

• Using list which doesn't map keys to counts
• Using TreeSet which stores unique sorted elements only
• Using LinkedList which is not key-value based

3. What is the output of the following Java code snippet?

String s = "swiss";
HashMap map = new HashMap<>();
for(char c : s.toCharArray()) {
  map.put(c, map.getOrDefault(c, 0) + 1);
}
for(char c : s.toCharArray()) {
  if(map.get(c) == 1) {
    System.out.println(c);
    break;
  }
}

medium

A. w

B. s

C. i

D. No output

Solution

1. Step 1: Count character frequencies

   Characters and counts: s=3, w=1, i=1.

2. Step 2: Find first character with count 1

   Iterate string: 's'(3), 'w'(1) -> first non repeating is 'w'.

3. Final Answer:

   w -> Option A

4. Quick Check:

   First unique char in "swiss" = w [OK]

Hint: Check counts then first unique char in order [OK]

Common Mistakes:

• Choosing 's' which repeats
• Choosing 'i' which is unique but appears after 'w'
• Assuming no output if not careful

4. Identify the error in this code snippet for finding the first non repeating character:

String s = "hello";
HashMap map = new HashMap<>();
for(int i = 0; i < s.length(); i++) {
  map.put(s.charAt(i), 1);
}
for(int i = 0; i < s.length(); i++) {
  if(map.get(s.charAt(i)) == 1) {
    System.out.println(s.charAt(i));
    break;
  }
}

medium

A. The map.put always sets count to 1, ignoring repeats

B. The loop should start from 1, not 0

C. The map should use Character keys, not int

D. The break statement is missing

Solution

1. Step 1: Analyze map population logic

   The code sets count to 1 for every character without incrementing, so repeats are not counted.

2. Step 2: Effect on finding non repeating character

   Since all counts are 1, the code incorrectly treats all characters as unique.

3. Final Answer:

   The map.put always sets count to 1, ignoring repeats -> Option A

4. Quick Check:

   Count update missing causes wrong results [OK]

Hint: Increment count instead of setting 1 every time [OK]

Common Mistakes:

• Not incrementing counts in map
• Wrong loop indices
• Confusing key types in map

5. Given the string "aabbccddeeffg", which character will be the first non repeating character using the hash method? What if the string is "aabbccddeeffggh"?

hard

A. First: g, Second: g

B. First: a, Second: h

C. First: g, Second: h

D. First: h, Second: h

Solution

1. Step 1: Analyze first string "aabbccddeeffg"

   All characters except 'g' appear twice; 'g' appears once, so first non repeating is 'g'.

2. Step 2: Analyze second string "aabbccddeeffggh"

   Now 'g' appears twice, 'h' appears once, so first non repeating is 'h'.

3. Final Answer:

   First: g, Second: h -> Option C

4. Quick Check:

   Check counts carefully for each string [OK]

Hint: Check counts carefully; last unique changes with input [OK]

Common Mistakes:

• Assuming first character is always unique
• Ignoring updated counts in second string
• Confusing repeated characters as unique