[Leetcode] First Non-repeating character #387

Geekforgeeks Problem

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 '$'.

Example 1:

Input:
S = hello
Output: h
Explanation: In the given string, the
first character which is non-repeating
is h, as it appears first and there is
no other 'h' in the string.

Example 2:

Input:
S = zxvczbtxyzvy
Output: c
Explanation: In the given string, 'c' is
the character which is non-repeating. 

Your Task:
You only need to complete the function nonrepeatingCharacter() that takes string S as a parameter and returns the character. If there is no non-repeating character then return '$' .

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Number of distinct characters).
Note: N = |S|

Constraints:

1 <= N <= 103 

// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;


 // } Driver Code Ends

class Solution
{
    public:
    static constexpr int range = 26;
    //Function to find the first non-repeating character in a string.
    char nonrepeatingCharacter(string s)
    {
        vector<int> arr(range, 0);
        map<char, int> mp;
        map<char, int>::iterator itr;
       
        for (int i = 0; i < s.size() ; i++) {
            arr[s[i] - 'a']++;
            /*std::cout << "i " << i << "  s[i]  " 
                      << s[i] << "  s[i]-'a'  " << s[i] - 'a' 
                      << " arr[s[i]-'a'] " << arr[s[i]-'a']  << std::endl;*/
        }
        /*
        // Display the array value
        for (int i = 0; i < s.size(); i++) {
            std::cout << "s[" << i << "]:  " << s[i] 
                      << "  count  " <<  arr[s[i] - 'a'] << std::endl;
        } 
        */
        
        /* store the index as key and count as value. 
         * Insertion will be ordered based on key in map
         * as key is already in ascending order. */   
        for (int i = 0; i < s.size(); i++) {
             mp[s[i]] = arr[s[i] - 'a'];
        }
       
        /*    
        // Display key & value
        for (itr = mp.begin(); itr != mp.end(); itr++) {
            cout << itr->first << "  " << itr->second << endl;
        }
        */
        
        for (itr = mp.begin(); itr !=  mp.end(); itr++) {
            /* Check the first letter with one occurrence */
            if (itr->second == 1) {
                /* Return the corresponsing character. */
                return itr->first;
            }
        } 
        
       return '$';
    }

};

// { Driver Code Starts.

int main() {
	
	int T;
	cin >> T;
	
	while(T--)
	{
	
	    string S;
	    cin >> S;
	    Solution obj;
        char ans = obj.nonrepeatingCharacter(S);
        
        if(ans != '$')
	    cout << ans;
        else cout << "-1";
            
        cout << endl;
	    
	}
	
	return 0;
}
  // } Driver Code Ends

For Input:

hello

Your Output:

h

Expected Output:

h

Leetcode Problem

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

 

Example 1:

Input: s = "leetcode"
Output: 0

Example 2:

Input: s = "loveleetcode"
Output: 2

Example 3:

Input: s = "aabb"
Output: -1

 

Constraints:

• 1 <= s.length <= 105
• s consists of only lowercase English letters.

class Solution {
    static constexpr int range = 26;
public:
    int firstUniqChar(string s) {
        vector<int> arr(range, 0);
        
        map<int, int> uom;
        map<int, int>::const_iterator itr;
        
        for (int i = 0; i < s.size() ; i++) {
            arr[s[i] - 'a']++;
            /*std::cout << "i " << i << "  s[i]  " 
                      << s[i] << "  s[i]-'a'  " << s[i] - 'a' 
                      << " arr[s[i]-'a'] " << arr[s[i]-'a']  << std::endl;*/
        }
        /*
        // Display the array value
        for (int i = 0; i < s.size(); i++) {
            std::cout << "s[" << i << "]:  " << s[i] 
                      << "  count  " <<  arr[s[i] - 'a'] << std::endl;
        }
        */
        
        for (int i = 0; i < s.size(); i++) {
            uom[i] = arr[s[i] - 'a'];
        }
        
        /*
        // Display key & value
        for (itr = uom.begin(); itr != uom.end(); itr++) {
           cout << itr->first << "  " << itr->second << endl;
        }
        */
        
        for (itr = uom.begin(); itr !=  uom.end(); itr++) {
            if (itr->second == 1) {
                return itr->first;
            }
        } 
        return -1;
    }
};