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 Approach to find first non-repeating character of the string

The Brute-Force solution of this problem is to iterate over complete string, and for every character encountered, again iterate over complete string in nested loop 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 first non-repeating character of the string is as follows:

/* C++ Program to find first 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 Method to find first non-repeating character of the string

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 first non-repeating character of the string is as follows:

/*C++ Program to find 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.

Related Posts:

  1. Find Most Frequent Character of the String.
  2. Check Anagram Strings.
  3. Check Whether Given String is Palindromic Anagram or Not.
  4. Check Whether Given String is Panagram or Not.
  5. Find Most Frequent Element of the Array.
  6. Find Pair in an Array with Given Sum.
  7. Find First Repeating Element of an Array.
  8. Find Majority Element of an Array.
  9. Check whether given Parentheses String are Balanced Parentheses or Not.
  10. Next Greater Element
  11. Find Minimum number of bracket reversals required to make an expression balanced.
  12. Implement Queue Using Two Stacks.
  13. Merge Overlapping Intervals using Stacks
  14. Implement Stack Using Linked List
  15. Largest Rectangular Area in Histogram
  16. Length of Longest Valid Substring
  17. Reverse a String using Stack
  18. Implement two stacks in a single array
  19. Print Bracket Number
  20. Next Greater Frequency Element

You may also like...

Leave a Reply

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