Non Repeating Character

Difficulty: Easy
Accuracy: 40.43%
Submissions: 262K+Points: 2

Given a string s consisting of lowercase Latin Letters. Return the first non-repeating character in s. If there is no non-repeating character, return ‘$’.
Note: When you return ‘$’ driver code will output -1.

Examples:

Input: s = "geeksforgeeks"
Output: 'f'
Explanation: In the given string, 'f' is the first character in the string which does not repeat.

Input: s = "racecar"
Output: 'e'
Explanation: In the given string, 'e' is the only character in the string which does not repeat.

Input: s = "aabbccc"
Output: -1
Explanation: All the characters in the given string are repeating.

Constraints:
1 <= s.size() <= 10⁵

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

char firstNonRepeatingChar(const string& s) {
    // Step 1: Count frequencies of each character
    unordered_map<char, int> charCount;
    for (char c : s) {
        charCount[c]++;
    }

    // Step 2: Find the first non-repeating character
    for (char c : s) {
        if (charCount[c] == 1) {
            return c; // First non-repeating character found
        }
    }

    // Step 3: No non-repeating character
    return '$';
}

int main() {
    string s = "geeksforgeeks";
    char result = firstNonRepeatingChar(s);

    if (result == '$') {
        cout << -1 << endl; // Follow the note: '$' indicates no non-repeating character
    } else {
        cout << result << endl;
    }

    return 0;
}

To solve the problem of finding the first non-repeating character in a string, we can use an efficient approach by incorporating a hashmap (or an equivalent data structure) to count the frequency of characters in the string. Here’s the step-by-step solution:

Steps to Solve:

1. Count Character Frequencies:
   • Traverse the string and count the occurrences of each character.
   • Store the counts in a dictionary (or a hashmap).
2. Find the First Non-Repeating Character:
   • Traverse the string again, and for each character, check its frequency in the hashmap.
   • The first character with a frequency of 1 is the first non-repeating character.
3. Return the Result:
   • If no character has a frequency of 1, return $.

Algorithm Complexity:

1. Time Complexity:
   • Counting frequencies: O(n) (single traversal for the frequency hashmap).
   • Traversing again to find the first non-repeating character: O(n).
   • Total: O(n).
2. Space Complexity:
   • Storing frequencies in a hashmap requires O(26) (in the worst case, since there are only 26 lowercase Latin letters). This is O(1) space.