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

Concept Flow - First Non Repeating Character Using Hash

Start

↓

Create empty hash map

↓

Iterate over string characters

↓

Update count in hash map

↓

Iterate over string again

↓

Check if count is 1

↓

Return char

↓

If none found, return -1

↓

End

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

Execution Sample

DSA Javascript

function firstNonRepeatingChar(s) {
  const count = {};
  for (const char of s) {
    count[char] = (count[char] || 0) + 1;
  }
  for (const char of s) {
    if (count[char] === 1) return char;
  }
  return -1;
}

This code finds the first character in string s that appears only once.

Execution Table

Step	Operation	Character Processed	Hash Map State	Action	Result
1	Initialize hash map	-	{}	Create empty object	-
2	Count char	'a'	{'a':1}	Add 'a' with count 1	-
3	Count char	'b'	{'a':1,'b':1}	Add 'b' with count 1	-
4	Count char	'c'	{'a':1,'b':1,'c':1}	Add 'c' with count 1	-
5	Count char	'a'	{'a':2,'b':1,'c':1}	Increment 'a' count to 2	-
6	Count char	'b'	{'a':2,'b':2,'c':1}	Increment 'b' count to 2	-
7	Count char	'd'	{'a':2,'b':2,'c':1,'d':1}	Add 'd' with count 1	-
8	Find first non-repeating	'a'	{'a':2,'b':2,'c':1,'d':1}	Count 2, skip	-
9	Find first non-repeating	'b'	{'a':2,'b':2,'c':1,'d':1}	Count 2, skip	-
10	Find first non-repeating	'c'	{'a':2,'b':2,'c':1,'d':1}	Count 1, return 'c'	'c'
11	End	-	-	-	Return 'c'

💡 Found first character with count 1 at step 10, returned 'c'

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 10	Final
count	{}	{'a':1}	{'a':1,'b':1}	{'a':1,'b':1,'c':1}	{'a':2,'b':1,'c':1}	{'a':2,'b':2,'c':1}	{'a':2,'b':2,'c':1,'d':1}	{'a':2,'b':2,'c':1,'d':1}	{'a':2,'b':2,'c':1,'d':1}
current_char	-	'a'	'b'	'c'	'a'	'b'	'd'	'c'	-

Key Moments - 3 Insights

Why do we need to iterate over the string twice?

The first loop counts all characters. The second loop finds the first character with count 1. This order ensures we know all counts before deciding which is first non-repeating (see steps 2-7 and 8-10 in execution_table).

What if the string has no non-repeating characters?

If no character has count 1, the second loop finishes without returning. Then the function returns -1 at step 11, meaning no unique character found.

Why use a hash map instead of checking each character directly?

Using a hash map stores counts efficiently in one pass. Checking each character directly for uniqueness would be slower (nested loops). The hash map approach is faster and clearer (see hash map updates in steps 2-7).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the count of character 'b'?

A 1

B 3

C 2

D 0

💡 Hint

Check the 'Hash Map State' column at step 6 in execution_table.

At which step does the function return the first non-repeating character?

A Step 10

B Step 9

C Step 8

D Step 11

💡 Hint

Look for the step where 'Action' says 'return' in execution_table.

If the input string was 'aabbcc', what would the final return value be?

A 'a'

B -1

C 'c'

D 'b'

💡 Hint

Refer to key_moments about no non-repeating characters and the return at step 11.

Concept Snapshot

First Non Repeating Character Using Hash

1. Create empty hash map to count chars.
2. Loop over string, update counts.
3. Loop again, find first char with count 1.
4. Return that char or -1 if none.

This method uses two passes and O(n) time.

Full Transcript

This concept finds the first character in a string that does not repeat. It uses a hash map (an object) to count how many times each character appears. First, it loops over the string and updates counts in the hash map. Then, it loops again to find the first character with count exactly one. If found, it returns that character. Otherwise, it returns -1. The execution table shows each step: initializing the hash map, counting characters, and then checking counts to find the first unique character. The variable tracker shows how the hash map and current character change over time. Key moments clarify why two loops are needed, what happens if no unique character exists, and why a hash map is efficient. The visual quiz tests understanding of counts at specific steps, when the function returns, and the result for a string with no unique characters. This approach is simple, efficient, and clear for beginners to understand how to find the first non-repeating character using a hash map.

Practice

1. What is the main purpose of using a hash (object) in finding the first non repeating character in a string?

easy

A. To reverse the string

B. To sort the characters alphabetically

C. To remove duplicate characters from the string

D. To count the frequency of each character in the string

Solution

1. Step 1: Understand the role of hash in frequency counting

   A hash (object) stores each character as a key and counts how many times it appears in the string.

2. Step 2: Use frequency to find first non repeating character

   By checking the hash, we find the first character with count 1, which is the first non repeating character.

3. Final Answer:

   To count the frequency of each character in the string -> Option D

4. Quick Check:

   Hash counts characters = Frequency count [OK]

Hint: Use hash to count characters, then find first with count 1 [OK]

Common Mistakes:

• Trying to sort characters instead of counting
• Ignoring character frequency
• Using hash to reverse string

2. Which of the following is the correct syntax to initialize an empty hash (object) in JavaScript for counting characters?

easy

A. let hash = [];

B. let hash = {};

C. let hash = ();

D. let hash = '';

Solution

1. Step 1: Identify JavaScript object syntax

   In JavaScript, curly braces {} create an empty object, which is used as a hash for key-value pairs.

2. Step 2: Confirm correct initialization

   Using let hash = {}; correctly initializes an empty object for counting characters.

3. Final Answer:

   let hash = {}; -> Option B

4. Quick Check:

   Empty object = {} [OK]

Hint: Use {} to create empty object for hash in JavaScript [OK]

Common Mistakes:

• Using [] which creates an array, not an object
• Using () which is invalid syntax
• Using empty string '' which is not an object

3. What will be the output of the following code?

function firstNonRepeatingChar(str) {
  const hash = {};
  for (const ch of str) {
    hash[ch] = (hash[ch] || 0) + 1;
  }
  for (const ch of str) {
    if (hash[ch] === 1) return ch;
  }
  return '_';
}

console.log(firstNonRepeatingChar('swiss'));

medium

A. 'w'

B. 's'

C. 'i'

D. '_'

Solution

1. Step 1: Count character frequencies in 'swiss'

   Characters: s(3), w(1), i(1). Hash = {s:3, w:1, i:1}

2. Step 2: Find first character with count 1 in original order

   Order: s, w, i, s, s. First with count 1 is 'w'.

3. Final Answer:

   'w' -> Option A

4. Quick Check:

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

Hint: Check counts, then scan string for first count 1 char [OK]

Common Mistakes:

• Returning 's' which repeats
• Returning 'i' which is second unique
• Returning '_' which means no unique char

4. Identify the error in the following code snippet that tries to find the first non repeating character:

function firstNonRepeatingChar(str) {
  const hash = {};
  for (let i = 0; i <= str.length; i++) {
    const ch = str[i];
    hash[ch] = (hash[ch] || 0) + 1;
  }
  for (let i = 0; i < str.length; i++) {
    if (hash[str[i]] === 1) return str[i];
  }
  return '_';
}

medium

A. The hash is not initialized correctly

B. The second loop should use <= instead of <

C. The first loop uses <= instead of < causing undefined access

D. The return '_' is unreachable code

Solution

1. Step 1: Check loop conditions for index errors

   The first loop uses i <= str.length, which accesses str[str.length] (undefined), causing an error.

2. Step 2: Correct loop condition to i < str.length

   Changing to i < str.length prevents out-of-bounds access and correctly counts characters.

3. Final Answer:

   The first loop uses <= instead of < causing undefined access -> Option C

4. Quick Check:

   Loop index must be less than length [OK]

Hint: Use < not <= for string index loops to avoid undefined [OK]

Common Mistakes:

• Using <= causes out-of-range errors
• Ignoring loop boundary conditions
• Misunderstanding hash initialization

5. Given the string 'aabbccddeeffg', which modification to the code below will correctly return the first non repeating character?

function firstNonRepeatingChar(str) {
  const hash = {};
  for (const ch of str) {
    hash[ch] = (hash[ch] || 0) + 1;
  }
  for (const ch of str) {
    if (hash[ch] === 1) return ch;
  }
  return '_';
}

Options:
A) Change return '_' to return null
B) Add a check to ignore spaces in the string
C) Modify the function to return '_' if no unique character exists
D) Change the hash to store boolean instead of counts

hard

A. Change return '_' to return null

B. Add a check to ignore spaces in the string

C. Modify the function to return '_' if no unique character exists

D. Change the hash to store boolean instead of counts

Solution

1. Step 1: Analyze the string and current function behavior

   String 'aabbccddeeffg' has all characters repeated except 'g' which appears once.

2. Step 2: Confirm function returns '_' if no unique char

   The function already returns '_' if no unique character is found, which is correct behavior.

3. Step 3: Understand why changing return '_' to return null is better

   Changing return '_' to return null clearly indicates no unique character found, which is a better practice than returning a character that might be confused as valid.

4. Final Answer:

   Change return '_' to return null -> Option A

5. Quick Check:

   Return null when no unique char found is clearer [OK]

Hint: Return null to indicate no unique character found [OK]

Common Mistakes:

• Returning '_' which can be confused as a valid character
• Ignoring spaces when not needed
• Using boolean instead of counts loses frequency info