Find First Non-Repeating Character of the String

Find First Non-Repeating Character of the String” is a very important and popular problem asked in many technical interviews of product-based companies. 

Here, we are given a string of length ‘n’ and our task is to find the first non-repeating character of the string.

Example:

Input:
COMPUTERSCIENCE
Output:
The first non-repeating character of given string is O

There are various methods to find the first non-repeating character of the string. Some of them are:

METHOD 1: Brute-Force

The Brute-Force solution of this problem is to iterate over complete string, and for every character encountered, iterate over complete string and find the frequency of each character of the string. 

While finding the frequency of each character, if the frequency of the current character is 1, then that character is the first non-repeating character of the given string.

If for any character, the frequency is not 1, then there is no non-repeating character present in the string.

C++ Program to find the first non-repeating character is as follows:

/* C++ Program to find forrst non-repeating character of the string */
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string str;
    
  /* Scan the String */
  cout<<"Enter a string:\n";  
  getline(cin,str); 
  
  /* Count the frequency of each character of the string,
    and the first characrter encountered with frequency 1 
    will be result */
    char res;
    int flag = 0;
    for(int i = 0; i < str.length(); i++)
    {
        int count = 0;
        for(int j = 0; j < str.length(); j++)
        {
            if(str[i] == str[j])
            count++;
            if(count > 1)
            break;
        }
        if(count == 1)
        {
            res = str[i];
            flag = 1;
            break;
        }
    }
    /* Printing the Result */
    if(flag == 1)
    cout<<"The first non-repeating character of the given string is "<<res;
    else
    cout<<"There is no non-repeating character present in the string";
}
Output:
Enter a string: COMPUTERSCIENCE
The first non-repeating character of the given string is O
Time Complexity:
O(n^2), where n is the length of the string.

METHOD 2: Hashing

The more time efficient method to find the first non-repeating character of the string is hashed based. 

Create a hash map with key of char type and value of integer type. Iterate over the string and increment the value of every character.

Again, scan the string and for every character, if in the map, the character key-pair value is 1, then break the loop and print the character.

C++ Program to find the first non-repeating character is as follows:

/*C++ Program to find the first non-repeating character of the string*/  
#include<bits/stdc++.h>  
#define size 1000  
using namespace std;  
int main()  
{  
    string str;  
    cout<<"Enter a string:";  
    getline(cin,str);  
    int flag1 = 0;  
    /* Create a Hash Map */  
    map<char,int>mp;  
    /* For every character, increment the  
       key-pair value for that character */  
    for(int i = 0; i <  str.length(); i++)  
    {  
        mp[str[i]]++;  
    }  
    /* Check if key-pair valu1 of any character is 1 */  
    for(int i = 0; i < str.length(); i++)  
    {  
        /* If key-pair value of any character is 1, then  
        that characte is first non-repeating character*/  
        if(mp[str[i]] == 1)  
        {  
            flag1 = 1;  
            cout<<"\nThe first non-repeating character is "<<str[i];  
            break;  
        }  
    }  
    if(flag1 == 0)  
    {  
        cout<<"\nAll the characters in the string are repeating characters!!";  
    }  
}  
Output:
Enter a string: COMPUTERSCIENCE
The first non-repeating character is O
Time Complexity:
O(nlogn), where n is the length of the string, and ‘logn’ is for insertion and searching operation in map.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *