First Non Repeating Character Using Hash in DSA C - Time & Space Complexity

Time Complexity: First Non Repeating Character Using Hash

O(n)

Understanding Time Complexity

We want to know how the time to find the first non-repeating character changes as the input string gets longer.

How does the number of steps grow when the string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

char firstNonRepeatingChar(char *str) {
    int count[256] = {0};
    int i;
    int len = strlen(str);

    for (i = 0; i < len; i++) {
        count[(unsigned char)str[i]]++;
    }

    for (i = 0; i < len; i++) {
        if (count[(unsigned char)str[i]] == 1) {
            return str[i];
        }
    }

    return '\0';
}

This code counts how many times each character appears, then finds the first character that appears only once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two loops over the input string.
• How many times: Each loop runs once over all characters, so twice over the string length.

How Execution Grows With Input

As the string gets longer, the number of steps grows roughly twice as fast because we scan the string two times.

Input Size (n)	Approx. Operations
10	About 20 steps
100	About 200 steps
1000	About 2000 steps

Pattern observation: The operations grow linearly with input size, doubling because of two passes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the first non-repeating character grows directly in proportion to the string length.

Common Mistake

[X] Wrong: "Because there are two loops, the time complexity is O(n²)."

[OK] Correct: The loops run one after another, not nested, so their times add up, not multiply.

Interview Connect

Understanding how to analyze simple loops like this helps you explain your code clearly and shows you know how to reason about efficiency.

Self-Check

"What if we used a nested loop to check each character against all others? How would the time complexity change?"