First Non Repeating Character Using Hash in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of first non-repeating character index

What is the output of this C code that finds the index of the first non-repeating character in the string?

DSA C

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

int firstNonRepeatingChar(char *str) {
    int count[256] = {0};
    int i;
    for (i = 0; str[i]; i++) {
        count[(unsigned char)str[i]]++;
    }
    for (i = 0; str[i]; i++) {
        if (count[(unsigned char)str[i]] == 1) {
            return i;
        }
    }
    return -1;
}

int main() {
    char str[] = "swiss";
    int index = firstNonRepeatingChar(str);
    printf("%d\n", index);
    return 0;
}

A 1

B -1

C 0

D 3

💡 Hint

Check the frequency of each character and find the first with count 1.

The string "swiss" has characters: s(3), w(1), i(1). The first non-repeating character is 'w' at index 1.

❓ Predict Output

intermediate

Output of first non-repeating character index with different string

What is the output of this C code that finds the index of the first non-repeating character in the string?

DSA C

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

int firstNonRepeatingChar(char *str) {
    int count[256] = {0};
    int i;
    for (i = 0; str[i]; i++) {
        count[(unsigned char)str[i]]++;
    }
    for (i = 0; str[i]; i++) {
        if (count[(unsigned char)str[i]] == 1) {
            return i;
        }
    }
    return -1;
}

int main() {
    char str[] = "aabbcc";
    int index = firstNonRepeatingChar(str);
    printf("%d\n", index);
    return 0;
}

A 0

B -1

C 1

D 2

💡 Hint

All characters repeat, so no non-repeating character.

All characters appear twice, so the function returns -1 indicating no non-repeating character.

🔧 Debug

advanced

Identify the error in this code for first non-repeating character

What error will this C code produce when compiled or run?

DSA C

#include <stdio.h>

int firstNonRepeatingChar(char *str) {
    int count[256];
    int i;
    for (i = 0; i < 256; i++) {
        count[i] = 0;
    }
    for (i = 0; str[i]; i++) {
        count[(unsigned char)str[i]]++;
    }
    for (i = 0; str[i]; i++) {
        if (count[(unsigned char)str[i]] == 1) {
            return i;
        }
    }
    return -1;
}

int main() {
    char str[] = "hello";
    int index = firstNonRepeatingChar(str);
    printf("%d\n", index);
    return 0;
}

A Compilation error due to uninitialized array

B Runtime error due to negative array index

C No error, output is 0

D No error, output is 2

💡 Hint

Check how the array is initialized and how characters are used as indices.

The array count is initialized manually with a loop. For "hello", 'h' appears once at index 0, so output is 0. Characters have positive ASCII, no negative index issue. No error.

❓ Predict Output

advanced

Output of first non-repeating character index with mixed case

What is the output of this C code that finds the index of the first non-repeating character in the string with mixed case letters?

DSA C

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

int firstNonRepeatingChar(char *str) {
    int count[256] = {0};
    int i;
    for (i = 0; str[i]; i++) {
        count[(unsigned char)str[i]]++;
    }
    for (i = 0; str[i]; i++) {
        if (count[(unsigned char)str[i]] == 1) {
            return i;
        }
    }
    return -1;
}

int main() {
    char str[] = "aAbBABac";
    int index = firstNonRepeatingChar(str);
    printf("%d\n", index);
    return 0;
}

A 1

B 6

C -1

D 2

💡 Hint

Remember that uppercase and lowercase letters have different ASCII codes.

String "aAbBABac": a(3), A(2), b(1 at index 2), B(2), c(1). First non-repeating is 'b' at index 2.

🧠 Conceptual

expert

Why use a hash array for first non-repeating character?

Why is using a hash array (like int count[256]) efficient for finding the first non-repeating character in a string?

A Because it counts frequency in O(n) time and uses constant space for ASCII

B Because it sorts the string characters in O(n log n) time

C Because it uses recursion to find unique characters

D Because it stores characters in a linked list for quick access

💡 Hint

Think about how many times the string is scanned and the size of the frequency array.

Using a fixed-size array for ASCII characters allows counting frequencies in one pass (O(n)) and then finding the first unique character in another pass, both linear time. The space is constant (256 ints).

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