Find first non repeating character in a string in C++

March 25, 2022

Non Repeating Character in a String in C++

Here, we will discuss the program to find the first non repeating character in a String in C++ programming language. We will discuss different methods in this page.

Method Discussed :

Method 1 : Naive Approach
Method 2 : Using Two string Traversal method.
Method 3 : Using Hash-map, single traversal.

Let’s discuss them one by one in brief,

Method 1:

Declare a variable say flag, that will st to 1 if the duplicate element is founded.
Start iterating over the string str,
Set flag =0;
Run a loop from index 0 to len
Check if(str[i]==str[j] && (i!=j))
Then, set flag =1; and break the loop
Check if(flag==0)
Print the cahracter.
At last if(flag==1), print “No non-repeating character”

Method 1 : Code in C++

Run

#include<bits/stdc++.h>
using namespace std;

int main() {
 
 string str = "WelcometoProgramming";
 int len  = str.length();
 int flag;
 
 for(int i = 0; i < len; i++) {
 
     flag = 0; 
  
     for(int j = 0; j < len; j++) {
   
        if((str[i] == str[j]) && (i != j)) {
             flag = 1;
             break;
        }
     }
  
      if (flag == 0) {
          cout<<"First non-repeating character is "<<str[i];
          break;
      }
  
 }
 
 if (flag == 1) {
     cout<<"No non-repeating character";
 }
 
  return 0;
}

Output :

First non-repeating character is W

Method 2 :

Make a hash map that maps the characters to their frequency values.
Using a pointer, traverse the given string.
Increase the current character’s count in the hash map.
Now go back over the string and see if the current character has frequency=1.
Continue the traverse if the frequency is more than one.
If the loop is not broken, print the current character as the answer.
break the loop and print the current character as the answer.

Method 2 : Code in C++

Run

#include <bits/stdc++.h>
#define NO_OF_CHARS 256
using namespace std;

int* getCharCountArray(char* str)
{
    int* count = (int*)calloc(sizeof(int), NO_OF_CHARS);
    int i;
    for (i = 0; *(str + i); i++)
        count[*(str + i)]++;
    return count;
}
 
int firstNonRepeating(char* str)
{
    int* count = getCharCountArray(str);
    int index = -1, i;
 
    for (i = 0; *(str + i); i++) {
        if (count[*(str + i)] == 1) {
            index = i;
            break;
        }
    }
 
    free(count);
    return index;
}
 
int main()
{
    char str[] = "WelcometoProgramming";
    int index = firstNonRepeating(str);
    if (index == -1)
        cout<<"No non-repeating character";
    else
        cout<<"First non-repeating character is "<< str[index];
    getchar();
    return 0;
}

Output :

First non-repeating character is W

Method 3 :

Declare a hash map.
Start iterating over the string the store the frequency of each element in the map.
Again iterate over the string, and check if the value of that element in the map is one,
Then print that element.
Otherwise at last print “No non-repeating character”.

Method 3 : Code in C++

Run

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    string str = "WelcometoProgramming";
    int len = str.length(), flag=0;
    
    map<char, int>mp;
    for(int i=0; i<len; i++)
        mp[str[i]]++;
    
    
    for(int i=0; i<len; i++){
        if(mp[str[i]]==1){
             cout<<"First non-repeating character is "<< str[i];
             flag=1;
             break;
        }
        
    }
    
    
    if (flag== 0)
        cout<<"No non-repeating character";
    
    return 0;
}

Output :

First non-repeating character is W