C++ Program to Find the First Non-repeated Character in a String

1. Introduction

Strings are a fundamental data type in programming, and they often require various processing and manipulation techniques. A common question regarding strings is identifying the first non-repeated character. This problem tests the understanding of string manipulation and data structures like arrays or maps. In this post, we will explore a C++ program to find the first non-repeated character in a given string.

2. Program Overview

Our program will:

1. Take a string as input from the user.

2. Create an array to track the frequency of each character.

3. Traverse the string to update the frequency array.

4. Traverse the string again to identify the first non-repeated character using the frequency array.

5. Display the result.

3. Code Program

#include<iostream>
#include<vector>
using namespace std;

// Function to find the first non-repeated character in the string
char firstNonRepeatingChar(const string& str) {
    // Create a frequency array of size 256 (for extended ASCII set) initialized with 0
    vector<int> freq(256, 0);

    // Traverse the string to populate the frequency array
    for (char ch : str) {
        freq[ch]++;
    }

    // Traverse the string again to identify the first non-repeated character
    for (char ch : str) {
        if (freq[ch] == 1) {
            return ch;
        }
    }

    // Return a placeholder character if no non-repeated character is found
    return '-';
}

int main() {
    string inputStr;
    cout << "Enter the string: ";
    cin >> inputStr;

    char result = firstNonRepeatingChar(inputStr);
    if (result != '-') {
        cout << "The first non-repeated character is: " << result << endl;
    } else {
        cout << "All characters are repeated." << endl;
    }

    return 0;
}

Output:

Enter the string: success
The first non-repeated character is: u

4. Step By Step Explanation

1. We start by taking a string input from the user.

2. The firstNonRepeatingChar function initializes a frequency array of size 256 (accounting for all possible extended ASCII characters).

3. The function then traverses the input string to populate this frequency array.

4. We traverse the input string a second time, using the frequency array to identify and return the first non-repeated character.

5. If no such character is found, we return a placeholder character -.

6. In the main function, we display the result or notify the user if all characters are repeated.