Find First Non-Repeating Character in a String

📝 Problem Statement

Given a string A, find and return the index of the first non-repeating character.
If there is no such character, return -1.

📚 Constraints

• 1 ≤ |A| ≤ 10⁵

• A contains only lowercase English letters.

🎯 Objective

You are given a string like "aabbcdc".
You need to return the index of the first character that does not repeat in the string.
In this example, "d" is the first non-repeating character, at index 4.

💡 Approach

We can solve this efficiently in two passes using a frequency count.

1. First, count the frequency of each character using an array of size 26 (since the input contains only lowercase letters).

2. Then, iterate over the string again and return the index of the first character with frequency 1.

This approach is O(n) time and O(1) space (because the character set is fixed).

✅ C Code

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

int firstNonRepeatingCharIndex(char *str) {
    int freq[26] = {0}; // An integer array named freq of size 26, all initialized to 0
    int len = strlen(str); 

     // count frequency
    for (int i = 0; i < len; i++) {
        freq[str[i] - 'a']++; // Increment index for that character
    }

    // find first non-repeating character
    for (int i = 0; i < len; i++) {
        if (freq[str[i] - 'a'] == 1) {
            return i;
        }
    }
    return -1;
}

int main() {
    char str1[] = "aabbcdc";
    printf("Index: %d\n", firstNonRepeatingCharIndex(str1));  // Output: 5

    char str2[] = "aabbcc";
    printf("Index: %d\n", firstNonRepeatingCharIndex(str2));  // Output: -1

    return 0;
}

🧪 Example

Let's trace through the input "aawdd":

Step 1: Frequency Counting

• Position 0: 'a' → freq[0] = 1

• Position 1: 'a' → freq[0] = 2

• Position 2: 'w' → freq[22] = 1

• Position 3: 'd' → freq[3] = 1

• Position 4: 'd' → freq[3] = 2

Frequency Array After First Pass:

• freq[0] = 2 (character 'a')

• freq[3] = 2 (character 'd')

• freq[22] = 1 (character 'w')

• All other indices = 0

Step 2: Finding the First Non-Repeating Character

• Position 0: 'a' → freq[0] = 2 (not 1, continue)

• Position 1: 'a' → freq[0] = 2 (not 1, continue)

• Position 2: 'w' → freq[22] = 1 ✓ (found!)

⚠️ Common Mistakes

• Forgetting to check case sensitivity (this solution assumes only lowercase letters).

• Returning the character instead of its index.

• Using hash maps unnecessarily for small fixed alphabets.

⚠️ Edge Cases

1. Empty String: "" → Returns -1

2. All Characters Same: "aaaa" → Returns -1

3. Single Character: "a" → Returns 0

4. All Unique Characters: "abcd" → Returns 0

5. Non-Repeating at End: "aabbcd" → Returns 4

🏷️ Asked In

• Amazon

• Google

• Adobe

• Walmart Labs

• TCS Digital

• Samsung R&D

📚 References

1. Problem Origin & Variants

   • LeetCode – First Unique Character in a String

   • GeeksforGeeks – Find the first non-repeating character

   • InterviewBit – First Non-Repeating Character