First Non Repeating Character Using Hash in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a hash to find the first non-repeating character in a string?

Use a hash (like an array or dictionary) to count how many times each character appears, then find the first character with a count of one.

beginner

Why do we need two passes over the string when finding the first non-repeating character using a hash?

First pass counts characters, second pass finds the first character with count one.

beginner

In C, what data structure is commonly used as a hash to count characters for ASCII strings?

An integer array of size 256 (for all ASCII characters) is used to store counts indexed by character ASCII values.

intermediate

What is the time complexity of finding the first non-repeating character using a hash in a string of length n?

O(n) because we scan the string twice, but each scan is linear time.

beginner

What should the function return if all characters in the string repeat?

Return a special value like -1 or indicate no non-repeating character found.

What does the hash store when finding the first non-repeating character?

A Index of each character

B Count of each character

C Characters sorted alphabetically

D Length of the string

The hash stores how many times each character appears.

How many times do we scan the string in the hash method?

A Four times

B Once

C Three times

D Twice

First to count characters, second to find the first non-repeating.

What size array is typically used as a hash for ASCII characters in C?

A 128

B 1024

C 256

D 512

256 covers all ASCII characters.

If the string is "aabbcc", what should the function return?

A -1

B 1

C 0

D 2

All characters repeat, so return -1.

What is the time complexity of this method?

A O(n)

B O(n log n)

C O(n^2)

D O(1)

Two linear scans make it O(n).

Explain how to find the first non-repeating character in a string using a hash.

Think about counting first, then checking order.

Describe the advantages of using a hash to find the first non-repeating character compared to checking each character one by one.

Focus on efficiency and speed.