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.