First Non Repeating Character Using Hash in DSA Java - Execution Trace

Concept Flow - First Non Repeating Character Using Hash

Start with input string

↓

Create empty hash map for counts

↓

For each character in string

↓

Increment count in hash map

↓

For each character in string

↓

Check count in hash map

↓

Return char

↓

If none found, return special char or -1

↓

End

We count each character's frequency using a hash map, then find the first character with count 1.

Execution Sample

DSA Java

String s = "swiss";
Map<Character, Integer> countMap = new HashMap<>();
for (char c : s.toCharArray()) {
  countMap.put(c, countMap.getOrDefault(c, 0) + 1);
}
for (char c : s.toCharArray()) {
  if (countMap.get(c) == 1) return c;
}
return -1;

Counts characters in 'swiss' and returns the first non-repeating character.

Execution Table

Step	Operation	Character Processed	Hash Map State	Check Condition	Action	Result
1	Initialize	-	{}	-	-	-
2	Count char	s	{s=1}	-	Add s=1	-
3	Count char	w	{s=1, w=1}	-	Add w=1	-
4	Count char	i	{s=1, w=1, i=1}	-	Add i=1	-
5	Count char	s	{s=2, w=1, i=1}	-	Increment s to 2	-
6	Count char	s	{s=3, w=1, i=1}	-	Increment s to 3	-
7	Check char	s	{s=3, w=1, i=1}	count == 1?	No	Continue
8	Check char	w	{s=3, w=1, i=1}	count == 1?	Yes	Return 'w'
9	End	-	-	-	-	First non-repeating char is 'w'

💡 Returned 'w' at step 8 because its count is 1.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
countMap	{}	{s=1}	{s=1, w=1}	{s=1, w=1, i=1}	{s=2, w=1, i=1}	{s=3, w=1, i=1}	{s=3, w=1, i=1}	{s=3, w=1, i=1}	{s=3, w=1, i=1}
currentChar	-	s	w	i	s	s	s	w	-
returnedChar	-	-	-	-	-	-	-	w	w

Key Moments - 3 Insights

Why do we need two loops instead of one?

The first loop counts all characters, building the hash map (see steps 2-6). The second loop checks characters in original order to find the first with count 1 (steps 7-8). Doing both in one loop would miss order.

What if no character has count 1?

If no character count equals 1 in the second loop (step 7), the function returns -1 (step 9). This means all characters repeat.

Why do we use a hash map for counting?

A hash map stores counts for each character efficiently, allowing quick lookup during the second loop (see hash map states in steps 2-6 and 7-8).

Visual Quiz - 3 Questions

Look at the execution table, what is the hash map state after processing the third character?

A {s=1, w=1, i=1}

B {s=2, w=1, i=1}

C {s=1, w=2, i=1}

D {s=1, w=1}

💡 Hint

Check the 'Hash Map State' column at step 4 in the execution table.

At which step does the algorithm decide to return the first non-repeating character?

A Step 7

B Step 8

C Step 6

D Step 9

💡 Hint

Look at the 'Action' and 'Result' columns in the execution table for when the return happens.

If the input string was "aabbcc", what would the final returned value be?

A 'a'

B 'b'

C 'c'

D -1

💡 Hint

Refer to the key moment about what happens if no character has count 1.

Concept Snapshot

First Non Repeating Character Using Hash

1. Use a hash map to count each character's frequency.
2. Traverse string again to find first char with count 1.
3. Return that character or -1 if none found.

This preserves order and runs in O(n) time.

Full Transcript

This concept finds the first character in a string that does not repeat. We use a hash map to count how many times each character appears. First, we loop through the string and update counts in the hash map. Then, we loop again through the string in order to find the first character whose count is exactly one. If found, we return that character. If no such character exists, we return -1. This method ensures we find the first non-repeating character efficiently while preserving the original order of characters.

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