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

Time Complexity: First Non Repeating Character Using Hash

O(n)

Understanding Time Complexity

We want to find how long it takes to find the first character that appears only once in a string using a hash map.

How does the time needed grow as the string gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from collections import Counter

def first_non_repeating_char(s: str) -> int:
    count = Counter(s)  # Count each character
    for i, ch in enumerate(s):
        if count[ch] == 1:
            return i
    return -1
    

This code counts characters, then finds the first one that appears only once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Counting characters and then scanning the string again.
• How many times: Counting loops over all characters once; scanning again loops over all characters once.

How Execution Grows With Input

As the string gets longer, the counting and scanning both take longer, roughly doubling the work.

Input Size (n)	Approx. Operations
10	About 20 operations (count + scan)
100	About 200 operations
1000	About 2000 operations

Pattern observation: Operations grow roughly twice the input size, so growth is linear.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Since we scan twice, the time is O(n²)."

[OK] Correct: Each scan goes through the string once, so total work is about 2n, which is still O(n), not squared.

Interview Connect

Understanding this helps you explain how hashing speeds up searching tasks, a key skill in many coding challenges.

Self-Check

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