Non Repeating Character

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⁵

Approach 01:

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

class Solution {
public:
    char nonRepeatingChar(const string& inputString) {
        unordered_map<char, int> charFrequency;

        // Count frequency of each character
        for (char c : inputString) {
            charFrequency[c]++;
        }

        // Find the first non-repeating character
        for (char c : inputString) {
            if (charFrequency[c] == 1) {
                return c;
            }
        }

        return '$'; // Return -1 if no non-repeating character is found
    }
};

import collections

class Solution:
    def nonRepeatingChar(self, inputString):
        charFrequency = collections.Counter(inputString)
        for char in inputString:
            if charFrequency[char] == 1:
                return char
        return -1

Time Complexity

• Counting character frequencies:

  The first for loop iterates over all characters in the string inputString. Let the length of the string be \(N\). This step takes \(O(N)\).

• Finding the first non-repeating character:

  The second for loop also iterates over all \(N\) characters in the string to check if their frequency is 1. This step takes \(O(N)\).

• Overall Time Complexity:

  The overall time complexity is \(O(N)\), as both loops are linear and executed sequentially.

Space Complexity

• Frequency map:

  The unordered_map stores the frequency of each character in the string. In the worst case (all characters are unique), the map stores all \(N\) characters, making this step \(O(U)\), where \(U\) is the number of unique characters in the input string (at most \(N\)).

• Input string:

  The input string itself uses \(O(N)\) space, but this is not considered extra space as it is part of the input.

• Overall Space Complexity:

  The overall space complexity is \(O(U)\), which simplifies to \(O(N)\) in the worst case when all characters are unique.