First Non Repeating Character Using Hash in DSA C#

Mental Model

We want to find the first character in a string that appears only once by counting how many times each character 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.

string: h -> e -> l -> l -> o -> null
counts: {h:1, e:1, l:2, o:1}
↑ first unique char pointer

Dry Run Walkthrough

Input: string: "hello"

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

Step 1: Count characters: see 'h', add h:1

counts: {h:1}

Why: We need to know how many times each character appears

Step 2: Count characters: see 'e', add e:1

counts: {h:1, e:1}

Why: Keep counting all characters

Step 3: Count characters: see 'l', add l:1

counts: {h:1, e:1, l:1}

Why: Add new character count

Step 4: Count characters: see 'l' again, update l:2

counts: {h:1, e:1, l:2}

Why: Increment count for repeated character

Step 5: Count characters: see 'o', add o:1

counts: {h:1, e:1, l:2, o:1}

Why: Finish counting all characters

Step 6: Check characters in order: 'h' count is 1, select 'h'

first non repeating char = 'h'

Why: First character with count 1 is the answer

Result:

h

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    // Function to find first non repeating character
    static char FirstNonRepeatingChar(string s)
    {
        var counts = new Dictionary<char, int>();

        // Count each character's frequency
        foreach (char c in s)
        {
            if (counts.ContainsKey(c))
                counts[c]++;
            else
                counts[c] = 1;
        }

        // Find first character with count 1
        foreach (char c in s)
        {
            if (counts[c] == 1)
                return c;
        }

        return '\0'; // Return null char if none found
    }

    static void Main()
    {
        string input = "hello";
        char result = FirstNonRepeatingChar(input);
        if (result != '\0')
            Console.WriteLine(result);
        else
            Console.WriteLine("No non repeating character found");
    }
}

foreach (char c in s)

count each character's frequency in the dictionary

if (counts.ContainsKey(c)) counts[c]++; else counts[c] = 1;

increment count if character seen before, else initialize to 1

foreach (char c in s)

iterate string again to find first character with count 1

if (counts[c] == 1) return c;

return first character that appears only once

Output

h

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 dictionary

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

Edge Cases

empty string

returns '\0' and prints 'No non repeating character found'

DSA C#

return '\0'; // Return null char if none found

all characters repeating

returns '\0' and prints 'No non repeating character found'

DSA C#

return '\0'; // Return null char if none found

single character string

returns that character as it is non repeating

DSA C#

if (counts[c] == 1) return c;

When to Use This Pattern

When asked to find the first unique or non repeating element in a sequence, use a hash map to count frequencies and then scan to find the first with count one.

Common Mistakes

Mistake: Checking counts while counting characters instead of after counting all
Fix: Complete counting all characters first, then scan again to find the first unique

Mistake: Returning the first character with count 1 without preserving original order
Fix: Iterate over the original string again to preserve order when checking counts

Summary

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

Use when you need to identify the earliest unique character efficiently.

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

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