First Non Repeating Character Using Hash in DSA Typescript - 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 count in hash map

↓

Return char

↓

If none found, return -1

↓

End

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

Execution Sample

DSA Typescript

function firstNonRepeatingChar(s: string): string | number {
  const count: {[key: string]: number} = {};
  for (const ch of s) count[ch] = (count[ch] || 0) + 1;
  for (const ch of s) if (count[ch] === 1) return ch;
  return -1;
}

This code finds the first character in the string that appears only once using a hash map.

Execution Table

Step	Operation	Character	Hash Map State	Action	Result/Output
1	Initialize hash map	-	{}	Create empty map	-
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	Check first non-repeating	a	{"a":2,"b":2,"c":1,"d":1}	Count is 2, skip	-
9	Check first non-repeating	b	{"a":2,"b":2,"c":1,"d":1}	Count is 2, skip	-
10	Check first non-repeating	c	{"a":2,"b":2,"c":1,"d":1}	Count is 1, return 'c'	Output: '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 4	After Step 7	After Step 10	Final
count	{}	{"a":1}	{"a":1,"b":1,"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	c	d	c	c
output	-	-	-	-	c	c

Key Moments - 3 Insights

Why do we need to iterate over the string twice?

The first iteration counts all characters. The second iteration finds the first character with count 1. This ensures we return the earliest non-repeating character, as shown in steps 2-7 and then 8-10 in the execution table.

What if no character is non-repeating?

If no character has count 1, the second loop finishes without returning. Then the function returns -1 at step 11, indicating no non-repeating character was found.

Why do we use a hash map for counting?

A hash map lets us store counts for each character efficiently. We update counts in O(1) time per character, as seen in steps 2-7, making the solution fast and simple.

Visual Quiz - 3 Questions

Look at the execution table, what is the hash map state after counting the character 'c'?

A {"a":2,"b":2,"c":1}

B {"a":1,"b":1,"c":1}

C {"a":1,"b":1}

D {"a":2,"b":2,"c":2}

💡 Hint

Check step 4 in the execution table for the hash map state after counting 'c'.

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

A Step 8

B Step 9

C Step 10

D Step 11

💡 Hint

Look at the 'Action' and 'Result/Output' columns in the execution table to find when the character is returned.

If the input string was "aabbcc", what would the output be?

A -1

B "b"

C "a"

D "c"

💡 Hint

Refer to the key moment about no non-repeating character and the final return value.

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, return first char with count 1.
4. If none found, return -1.

This finds earliest unique char efficiently.

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 to find the first character with count one. If none is found, we return -1. The execution table shows each step: counting characters and then checking counts. The variable tracker shows how the hash map changes. Key moments explain why two loops are needed, what happens if no unique character exists, and why a hash map is used. The visual quiz tests understanding of the hash map state and output steps. This method is simple and efficient for this problem.

Practice

1. What is the main purpose of using a hash (like a dictionary or map) to find the first non-repeating character in a string?

easy

A. To count the frequency of each character efficiently

B. To sort the characters alphabetically

C. To reverse the string quickly

D. To remove duplicate characters from the string

Solution

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

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

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

   By checking the counts in order, we can find the first character with count 1, which is the first non-repeating character.

3. Final Answer:

   To count the frequency of each character efficiently -> Option A

4. Quick Check:

   Hash counts characters = To count the frequency of each character efficiently [OK]

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

Common Mistakes:

• Thinking hash sorts characters
• Trying to reverse string instead
• Assuming hash removes duplicates

2. Which of the following TypeScript code snippets correctly initializes a hash map to store character counts?

easy

A. const charCount = new Set<string>();

B. const charCount = new Array();

C. const charCount = new Map();

D. const charCount = new Object<number>();

Solution

1. Step 1: Identify correct TypeScript syntax for a map

   TypeScript uses Map to create a hash map. Here, keys are strings and values are numbers.

2. Step 2: Check each option for correctness

   const charCount = new Map(); uses Map(), which is correct. Options A, B, and D use incorrect types or structures.

3. Final Answer:

   const charCount = new Map<string, number>(); -> Option C

4. Quick Check:

   Map<string, number> is correct syntax [OK]

Hint: Use Map() to store char counts [OK]

Common Mistakes:

• Using Array instead of Map
• Using Set which stores only keys
• Incorrect Object initialization

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

function firstNonRepeatingChar(s: string): string {
  const count = new Map();
  for (const ch of s) {
    count.set(ch, (count.get(ch) ?? 0) + 1);
  }
  for (const ch of s) {
    if (count.get(ch) === 1) return ch;
  }
  return '_';
}
console.log(firstNonRepeatingChar('swiss'));

medium

A. '_'

B. 's'

C. 'i'

D. 'w'

Solution

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

   Characters: s(3), w(1), i(1). The map stores these counts.

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

   Order: 's' (count 3), 'w' (count 1), 'i' (count 1). The first with count 1 is 'w'.

3. Final Answer:

   'w' -> Option D

4. Quick Check:

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

Hint: Check counts in order, first with 1 is answer [OK]

Common Mistakes:

• Choosing first character without checking count
• Confusing 'i' and 'w'
• Returning '_' when unique char exists

4. Identify the bug in this TypeScript function to find the first non-repeating character:

function firstNonRepeatingChar(s: string): string {
  const count = new Map();
  for (let i = 0; i <= s.length; i++) {
    const ch = s[i];
    count.set(ch, (count.get(ch) ?? 0) + 1);
  }
  for (const ch of s) {
    if (count.get(ch) === 1) return ch;
  }
  return '_';
}

medium

A. Map should be initialized with Object instead of Map

B. Loop condition should be i < s.length, not i <= s.length

C. Return '_' should be inside the first loop

D. Use 'for...in' instead of 'for...of' for string iteration

Solution

1. Step 1: Check the for loop boundary

   The loop runs from i = 0 to i <= s.length, which accesses s[s.length], an undefined index causing error.

2. Step 2: Correct loop condition

   Change condition to i < s.length to avoid out-of-bounds access and correctly count characters.

3. Final Answer:

   Loop condition should be i < s.length, not i <= s.length -> Option B

4. Quick Check:

   Loop boundary off by one error [OK]

Hint: Use i < length, not i <= length in loops [OK]

Common Mistakes:

• Off-by-one error in loop condition
• Misusing Map initialization
• Wrong loop type for string iteration

5. Given the string 'aabbccddeeffg', which modification to the hash-based approach will correctly return the first non-repeating character when some characters appear multiple times and some only once?

hard

A. After counting, iterate the string and return the first character with count 1

B. Sort the string and return the first character

C. Return the character with the highest count from the hash

D. Return the last character in the string regardless of counts

Solution

1. Step 1: Count frequencies of all characters

   Use a hash map to count how many times each character appears in the string.

2. Step 2: Iterate string in original order to find first count 1

   Check each character in order; the first with count 1 is the first non-repeating character.

3. Final Answer:

   After counting, iterate the string and return the first character with count 1 -> Option A

4. Quick Check:

   Count then check order for first unique char [OK]

Hint: Count all, then find first with count 1 in order [OK]

Common Mistakes:

• Sorting string loses original order
• Returning highest count instead of unique
• Ignoring character order in result