First Non Repeating Character Using Hash in DSA C# - Execution Trace

Concept Flow - First Non Repeating Character Using Hash

Start with input string

↓

Create empty hash map for counts

↓

For each char in string

↓

Increment char count in hash

↓

For each char in string again

↓

Check if char count is 1?

No→Continue

Yes↓

Return this char as first non repeating

↓

If none found, return special value

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

Execution Sample

DSA C#

string s = "swiss";
Dictionary<char,int> counts = new Dictionary<char,int>();
foreach(char c in s) {
  if(counts.ContainsKey(c)) {
    counts[c]++;
  } else {
    counts[c] = 1;
  }
}
foreach(char c in s) {
  if(counts[c] == 1) return c;
}
return '\0';

Counts characters in 'swiss' then finds first non repeating character.

Execution Table

Step	Operation	Character Processed	Hash Map State	Action	Result/Visual State
1	Initialize hash map	-	{}	Create empty dictionary	{}
2	Count char	s	{'s':1}	Add 's' with count 1	{'s':1}
3	Count char	w	{'s':1, 'w':1}	Add 'w' with count 1	{'s':1, 'w':1}
4	Count char	i	{'s':1, 'w':1, 'i':1}	Add 'i' with count 1	{'s':1, 'w':1, 'i':1}
5	Count char	s	{'s':2, 'w':1, 'i':1}	Increment 's' count to 2	{'s':2, 'w':1, 'i':1}
6	Count char	s	{'s':3, 'w':1, 'i':1}	Increment 's' count to 3	{'s':3, 'w':1, 'i':1}
7	Find first non repeating	s	{'s':3, 'w':1, 'i':1}	Check count of 's' (3)	Not 1, continue
8	Find first non repeating	w	{'s':3, 'w':1, 'i':1}	Check count of 'w' (1)	Count is 1, return 'w'
9	End	-	-	-	First non repeating char is 'w'

💡 Found 'w' with count 1 at step 8, so returned as first non repeating character.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 8	Final
counts	{}	{'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}
current_char	-	s	w	i	s	s	w	w
result	null	null	null	null	null	null	'w'	'w'

Key Moments - 3 Insights

Why do we need to count all characters first before finding the first non repeating?

Because we must know the total count of each character before deciding which one appears only once. The execution_table rows 2-6 show counting all chars first, then rows 7-8 check counts to find the first non repeating.

Why do we check characters in the original string order again after counting?

To find the first character with count 1 in the original order. The hash map stores counts but does not keep order. The second loop (rows 7-8) preserves order to find the first unique.

What if no character has count 1?

Then after checking all characters, no return happens and a special value (like null or -1) is returned. This is implied after step 9 in the execution_table where no unique char is found.

Visual Quiz - 3 Questions

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

A {'s':2, 'w':1, 'i':1}

B {'s':1, 'w':1, 'i':1}

C {'s':1, 'w':1}

D {}

💡 Hint

Check row 4 in execution_table under 'Hash Map State' after processing 'i'.

At which step does the algorithm find the first non repeating character?

A Step 8

B Step 7

C Step 6

D Step 9

💡 Hint

Look at the 'Action' and 'Result' columns in execution_table rows 7 and 8.

If the input string was "aabbcc", how would the hash map counts change after counting all characters?

A {'a':1, 'b':1, 'c':1}

B {}

C {'a':2, 'b':2, 'c':2}

D {'a':3, 'b':3, 'c':3}

💡 Hint

Refer to variable_tracker counts after counting characters, similar to steps 2-6.

Concept Snapshot

First Non Repeating Character Using Hash

1. Traverse string, count chars in hash map.
2. Traverse string again, check counts.
3. Return first char with count 1.
4. If none, return special value.

Uses O(n) time and O(1) space (fixed char set).

Full Transcript

This concept finds the first character in a string that does not repeat. We first create an empty hash map to count how many times each character appears. We go through the string once, updating counts for each character. Then, we go through the string again in order, checking the counts in the hash map. The first character with count 1 is returned as the first non repeating character. If no such character exists, a special value is returned. The execution table shows each step of counting and checking. The variable tracker shows how the counts and current character change. Key moments clarify why counting first is necessary and why order matters. The visual quiz tests understanding of hash map states and steps where the result is found.

Practice

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

easy

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

B. To sort the characters alphabetically

C. To reverse the string quickly

D. To store the string length

Solution

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

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

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

   By checking the counts, 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 in the string -> Option A

4. Quick Check:

   Hash = frequency map [OK]

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

Common Mistakes:

• Trying to sort characters instead of counting
• Using hash to store indexes only
• Ignoring character frequency

2. Which of the following C# code snippets correctly initializes a dictionary to count character frequencies for a string input?

easy

A. var freq = new Dictionary(); foreach (char c in input) { if (freq.ContainsKey(c)) freq[c]++; else freq[c] = 1; }

B. var freq = new Dictionary(); foreach (char c in input) { freq[c] = 1; }

C. var freq = new List<int>(); foreach (char c in input) { freq.Add(c); }

D. var freq = new Dictionary(); foreach (char c in input) { freq[c] = c.ToString(); }

Solution

1. Step 1: Check dictionary key and value types

   We need a dictionary with char keys and int values to count frequencies.

2. Step 2: Verify frequency counting logic

   var freq = new Dictionary(); foreach (char c in input) { if (freq.ContainsKey(c)) freq[c]++; else freq[c] = 1; } correctly checks if the character exists and increments count or sets it to 1.

3. Final Answer:

   var freq = new Dictionary(); foreach (char c in input) { if (freq.ContainsKey(c)) freq[c]++; else freq[c] = 1; } -> Option A

4. Quick Check:

   Correct dictionary type and counting logic [OK]

Hint: Use Dictionary and increment counts properly [OK]

Common Mistakes:

• Using wrong dictionary types
• Not incrementing counts correctly
• Using List instead of Dictionary

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

string input = "swiss";
var freq = new Dictionary();
foreach (char c in input) {
  if (freq.ContainsKey(c)) freq[c]++;
  else freq[c] = 1;
}
char result = '\0';
foreach (char c in input) {
  if (freq[c] == 1) {
    result = c;
    break;
  }
}
Console.WriteLine(result == '\0' ? "None" : result);

medium

A. i

B. s

C. w

D. None

Solution

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

   s appears 3 times, w appears 1 time, i appears 1 time.

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

   Order is s, w, i, s, s. The first with count 1 is 'w'.

3. Final Answer:

   w -> Option C

4. Quick Check:

   First unique char = w [OK]

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

Common Mistakes:

• Choosing 'i' because it is unique but not first
• Choosing 's' which repeats
• Printing None incorrectly

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

string input = "hello";
var freq = new Dictionary();
foreach (char c in input) {
  freq[c] = freq[c] + 1;
}
char result = '\0';
foreach (char c in input) {
  if (freq[c] == 1) {
    result = c;
    break;
  }
}
Console.WriteLine(result == '\0' ? "None" : result);

medium

A. The result variable is not initialized

B. freq[c] is used before initialization causing KeyNotFoundException

C. The loop does not iterate over the string

D. The output statement is missing

Solution

1. Step 1: Analyze frequency counting loop

   The code tries to increment freq[c] without checking if c exists in dictionary, causing error.

2. Step 2: Identify correct fix

   Must check if freq contains c before incrementing or initialize freq[c] to 1 if missing.

3. Final Answer:

   freq[c] is used before initialization causing KeyNotFoundException -> Option B

4. Quick Check:

   Accessing uninitialized key causes error [OK]

Hint: Always check key exists before incrementing dictionary value [OK]

Common Mistakes:

• Assuming dictionary auto-initializes keys
• Ignoring exception details
• Missing initialization logic

5. Given the string input = "aabbccddeeffg", which character will be the first non-repeating character using a hash-based approach? If none exists, return 'None'.

hard

A. f

B. a

C. None

D. g

Solution

1. Step 1: Count frequencies of each character

   Characters a,b,c,d,e,f appear twice each; g appears once.

2. Step 2: Find first character with frequency 1 in string order

   String order is a,a,b,b,c,c,d,d,e,e,f,f,g. The first with count 1 is 'g'.

3. Final Answer:

   g -> Option D

4. Quick Check:

   Only 'g' is unique and first non-repeating [OK]

Hint: Check counts, then scan string order for first unique char [OK]

Common Mistakes:

• Choosing 'None' incorrectly
• Picking repeated characters
• Ignoring last unique character