Find Non Repeating Character In String In C Program

Identifying non-repeating characters in a string is a common problem in programming, useful for various string manipulation tasks. In this article, you will learn how to approach and solve this problem in C, exploring different methods to find the first character that appears only once.

Problem Statement

The challenge is to find the very first character within a given string that does not have any duplicate occurrences throughout the entire string. This means we are looking for a character that appears exactly once, and among all such characters, we need the one that shows up earliest in the string.

For instance, in the string "programming", 'p' appears twice, 'r' appears twice, 'o' appears once, 'g' appears twice, 'a' appears once, 'm' appears twice, 'i' appears once, 'n' appears once. The non-repeating characters are 'o', 'a', 'i', 'n'. The first among these is 'o'.

Example

Let's consider the string "swiss".

• 's' appears 3 times.
• 'w' appears 1 time.
• 'i' appears 1 time.

The first non-repeating character in "swiss" is 'w'.

Background & Knowledge Prerequisites

To effectively understand and implement the solutions, you should have a basic understanding of:

• C Programming Fundamentals: Variables, data types, loops (for, while), conditional statements (if-else).
• Strings in C: How strings are represented as character arrays, null-termination (\0), and basic string manipulation.
• Arrays: Declaring and using arrays to store data.
• ASCII Character Set: Understanding that characters can be mapped to integer values, which is useful for frequency counting.

Use Cases or Case Studies

Finding non-repeating characters has several practical applications:

• Data Validation: In user input, identifying unique characters can be part of validation rules, such as checking for distinct characters in a password.
• Text Processing: Analyzing text for unique words or characters can be useful in natural language processing (NLP) tasks like sentiment analysis or tokenization.
• Cryptography: Some basic cryptographic algorithms might use unique character properties for encoding or decoding messages.
• Puzzle Solving: Many coding challenges and brain teasers involve identifying unique or non-repeating elements in sequences.
• Log Analysis: Quickly finding unique events or identifiers in a stream of log data.

Solution Approaches

We will explore two common approaches to solve this problem: a brute-force method using nested loops and a more efficient method using a frequency array.

Approach 1: Brute-Force with Nested Loops

This approach iterates through each character of the string and, for each character, checks the rest of the string to see if it has any duplicates.

• Summary: For every character, check its count by iterating through the entire string again.

// Find First Non-Repeating Character (Brute-Force)
#include <stdio.h>
#include <string.h> // For strlen

int main() {
    char str[] = "programming"; // Example string
    int len = strlen(str);
    char firstNonRepeating = '\\0'; // Initialize with null character

    // Step 1: Iterate through each character of the string
    for (int i = 0; i < len; i++) {
        int count = 0; // Reset count for current character
        
        // Step 2: For each character, iterate through the string again to count occurrences
        for (int j = 0; j < len; j++) {
            if (str[i] == str[j]) {
                count++;
            }
        }
        
        // Step 3: If a character appears exactly once, it's a non-repeating character
        if (count == 1) {
            firstNonRepeating = str[i]; // Store it as the first found
            break; // Since we need the *first* one, we can stop
        }
    }

    // Step 4: Print the result
    if (firstNonRepeating != '\\0') {
        printf("The first non-repeating character is: %c\\n", firstNonRepeating);
    } else {
        printf("No non-repeating character found.\\n");
    }

    return 0;
}

Run

Sample Output:

The first non-repeating character is: o

Stepwise Explanation:

1. Initialize firstNonRepeating to \0 (null character) to signify no character found yet.
2. The outer loop (for (int i = 0; i < len; i++)) picks each character of the string one by one.
3. For each character str[i], an inner loop (for (int j = 0; j < len; j++)) scans the entire string again to count how many times str[i] appears.
4. If count for str[i] is exactly 1, it means str[i] is a non-repeating character. Since the outer loop progresses from left to right, the first one found will indeed be the *first* non-repeating character in the string.
5. Store this character in firstNonRepeating and break out of the outer loop immediately.
6. Finally, print the character found or a message indicating none was found.

Approach 2: Using a Frequency Array (Hash Map Concept)

This approach uses an auxiliary array to store the frequency of each character. This is more efficient as it reduces the time complexity.

• Summary: Populate a frequency array in one pass, then iterate through the string again to find the first character with a frequency of 1.

// Find First Non-Repeating Character (Frequency Array)
#include <stdio.h>
#include <string.h> // For strlen

#define MAX_CHARS 256 // Assuming ASCII characters

int main() {
    char str[] = "aabbcdeff"; // Example string
    int len = strlen(str);
    int freq[MAX_CHARS] = {0}; // Initialize all frequencies to 0

    // Step 1: First pass - Populate the frequency array
    // Iterate through the string and count occurrences of each character
    for (int i = 0; i < len; i++) {
        // Increment count for the character at its ASCII value index
        freq[(unsigned char)str[i]]++; 
    }

    char firstNonRepeating = '\\0'; // Initialize with null character

    // Step 2: Second pass - Find the first character with frequency 1
    // Iterate through the string again, in order, to find the first character
    // whose count in the freq array is 1.
    for (int i = 0; i < len; i++) {
        if (freq[(unsigned char)str[i]] == 1) {
            firstNonRepeating = str[i];
            break; // Found the first non-repeating, no need to continue
        }
    }

    // Step 3: Print the result
    if (firstNonRepeating != '\\0') {
        printf("The first non-repeating character is: %c\\n", firstNonRepeating);
    } else {
        printf("No non-repeating character found.\\n");
    }

    return 0;
}

Run

Sample Output:

The first non-repeating character is: c

Stepwise Explanation:

1. Declare an integer array freq of size MAX_CHARS (256 for ASCII characters) and initialize all its elements to 0. This array will store the count of each character.
2. First Pass: Iterate through the input string. For each character str[i], use its ASCII value as an index into the freq array and increment the count at that index. For example, if str[i] is 'a', freq['a'] will be incremented.
3. Initialize firstNonRepeating to \0.
4. Second Pass: Iterate through the input string *again*. This time, for each character str[i], check its count in the freq array.
5. If freq[(unsigned char)str[i]] is 1, it means this character appears only once in the entire string. Since we are iterating through the string from left to right, this will be the *first* such non-repeating character.
6. Store this character in firstNonRepeating and break out of the loop.
7. Finally, print the result.

Conclusion

Finding the first non-repeating character in a string can be approached in several ways, each with its own trade-offs. The brute-force method, while straightforward, involves nested loops resulting in higher time complexity. The frequency array method offers a more efficient solution by using an auxiliary data structure to count character occurrences in two passes, making it generally preferred for larger strings.

Summary

• The problem requires finding the character that appears exactly once and is encountered earliest in the string.
• Brute-Force Method: Uses nested loops to check each character's count, simple to understand but less efficient (O(N^2) time complexity).
• Frequency Array Method: Employs an array to store character counts in one pass, then a second pass identifies the first character with a count of one (O(N) time complexity, more efficient).
• Both methods involve iterating through the string, but the frequency array optimizes the counting process.
• Understanding character ASCII values is key for the frequency array approach.