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 line of people where some people appear multiple times. We want to find the first person who is standing alone without any twins behind or ahead.

string: h -> e -> l -> l -> o -> null
hash: [h:1, e:1, l:2, o:1]

Dry Run Walkthrough

Input: string: "hello"

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

Step 1: Count frequency of 'h'

hash: [h:1]

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

Step 2: Count frequency of 'e'

hash: [h:1, e:1]

Why: Continue counting to build full frequency map

Step 3: Count frequency of 'l'

hash: [h:1, e:1, l:1]

Why: Add 'l' first time

Step 4: Count frequency of second 'l'

hash: [h:1, e:1, l:2]

Why: Increment count for repeated 'l'

Step 5: Count frequency of 'o'

hash: [h:1, e:1, l:2, o:1]

Why: Complete frequency map

Step 6: Scan string from start to find first char with count 1

string: h -> e -> l -> l -> o -> null
first non repeating char: 'h'

Why: First character with count 1 is the answer

Result:

h

Annotated Code

DSA C

#include <stdio.h>
#include <string.h>

#define CHAR_RANGE 256

char firstNonRepeatingChar(const char *str) {
    int freq[CHAR_RANGE] = {0};
    int length = strlen(str);

    // Count frequency of each character
    for (int i = 0; i < length; i++) {
        freq[(unsigned char)str[i]]++;
    }

    // Find first character with frequency 1
    for (int i = 0; i < length; i++) {
        if (freq[(unsigned char)str[i]] == 1) {
            return str[i];
        }
    }

    return '\0'; // No non repeating character found
}

int main() {
    const char *input = "hello";
    char result = firstNonRepeatingChar(input);
    if (result != '\0') {
        printf("%c\n", result);
    } else {
        printf("No non repeating character found\n");
    }
    return 0;
}

freq[(unsigned char)str[i]]++;

increment frequency count for current character

if (freq[(unsigned char)str[i]] == 1) {

check if current character appears only once

return str[i];

return first non repeating character found

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(1) because frequency array size is fixed (256) regardless of input size

vs Alternative: Compared to checking each character against all others (O(n^2)), this hash method is much faster and efficient

Edge Cases

empty string

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

DSA C

return '\0'; // No non repeating character found

all characters repeating

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

DSA C

return '\0'; // No non repeating character found

string with one character

returns that character as it is non repeating

DSA C

if (freq[(unsigned char)str[i]] == 1) {

When to Use This Pattern

When asked to find the first unique or non repeating character in a string, use a frequency count hash to quickly identify it in linear time.

Common Mistakes

Mistake: Using nested loops to check each character against all others causing O(n^2) time
Fix: Use a frequency array or hash map to count characters in one pass, then find the first unique in another pass

Mistake: Not handling empty string or no unique character cases
Fix: Return a special value like '\0' and check for it in the driver code

Summary

Finds the first character in a string that appears only once using a frequency count.

Use when you need to quickly identify the first unique character in a string.

Counting frequencies first then scanning preserves order and gives O(n) time.

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 reverse the string quickly

B. To sort the characters alphabetically

C. To remove duplicate characters from the string

D. To count the frequency of each character efficiently

Solution

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

   A hash (dictionary) stores characters as keys and their counts as values, allowing quick frequency counting.

2. Step 2: Identify why frequency counting helps

   Knowing how many times each character appears helps 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 D

4. Quick Check:

   Hash counts characters = frequency count [OK]

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

Common Mistakes:

• Thinking hash sorts characters
• Assuming hash reverses string
• Using hash to remove duplicates only

2. Which of the following C code snippets correctly initializes a hash map (using an array) to count characters for ASCII strings?

easy

A. int count[256] = {0};

B. int count[] = NULL;

C. int count[256]; // uninitialized

D. int count = 256;

Solution

1. Step 1: Check correct array initialization

   In C, to count ASCII chars, an int array of size 256 initialized to zero is needed: int count[256] = {0};

2. Step 2: Identify incorrect options

   int count[] = NULL; sets pointer to NULL, no array. int count[256]; // uninitialized is uninitialized, may contain garbage. int count = 256; is a single int, not array.

3. Final Answer:

   int count[256] = {0}; -> Option A

4. Quick Check:

   Array size 256 with zero init = correct hash map [OK]

Hint: Use int count[256] = {0} for ASCII char frequency [OK]

Common Mistakes:

• Not initializing array to zero
• Using pointer instead of array
• Declaring single int instead of array

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

char str[] = "swiss";
int count[256] = {0};
for (int i = 0; str[i] != '\0'; i++) {
    count[(int)str[i]]++;
}
for (int i = 0; str[i] != '\0'; i++) {
    if (count[(int)str[i]] == 1) {
        printf("%c", str[i]);
        break;
    }
}

medium

A. s

B. i

C. w

D. No output

Solution

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

   Characters: s(3 times), w(1 time), i(1 time)

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

   Order: s (count 3), w (count 1) -> first non-repeating is 'w'

3. Final Answer:

   w -> Option C

4. Quick Check:

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

Hint: Check counts, print first char with count 1 [OK]

Common Mistakes:

• Printing first char without checking count
• Confusing 'i' and 'w' counts
• Ignoring character order

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

char str[] = "hello";
int count[256];
for (int i = 0; str[i] != '\0'; i++) {
    count[(int)str[i]]++;
}
for (int i = 0; str[i] != '\0'; i++) {
    if (count[(int)str[i]] == 1) {
        printf("%c", str[i]);
        break;
    }
}

medium

A. count array is not initialized to zero

B. Loop condition is incorrect

C. Casting char to int is wrong

D. printf format specifier is incorrect

Solution

1. Step 1: Check count array initialization

   count array is declared but not initialized, so it contains garbage values causing wrong counts.

2. Step 2: Explain impact of uninitialized array

   Incrementing garbage values leads to incorrect frequency counts, so first non-repeating char cannot be found correctly.

3. Final Answer:

   count array is not initialized to zero -> Option A

4. Quick Check:

   Uninitialized count array causes wrong frequency [OK]

Hint: Always initialize count array to zero before counting [OK]

Common Mistakes:

• Forgetting to initialize count array
• Assuming default zero initialization
• Misusing loop conditions

5. Given the string "aabbccddeffg", which character will be identified as the first non-repeating character using a hash map counting method? Consider the code below:

char str[] = "aabbccddeffg";
int count[256] = {0};
for (int i = 0; str[i] != '\0'; i++) {
    count[(int)str[i]]++;
}
for (int i = 0; str[i] != '\0'; i++) {
    if (count[(int)str[i]] == 1) {
        printf("%c", str[i]);
        break;
    }
}

hard

A. g

B. e

C. d

D. f

Solution

1. Step 1: Count frequencies of each character

   Characters and counts: a(2), b(2), c(2), d(2), e(1), f(2), g(1)

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

   Order: a,b,c,d,e,f,g; e and g have count 1, but e appears before g.

3. Step 3: Check carefully the string order

   String is "aabbccddeffg"; 'e' appears once at position 8, 'g' at position 11. So first non-repeating is 'e'.

4. Final Answer:

   e -> Option B

5. Quick Check:

   First unique char in string = e [OK]

Hint: Check counts and order carefully to find first unique char [OK]

Common Mistakes:

• Choosing last unique char instead of first
• Ignoring character order in string
• Miscounting character frequencies