Find the first repeated character in a string in C++

This article will guide you on how to write an efficient program to find the repeated character present first in the string. To understand better, let us see some examples. If the input string is:

1) str=”abbcc”, then the output will be b because b is the first character which is repeated.

2) str=”abcd”.

Here, all the characters are distinct and no character is repeated and if no character is repeated, we want the output to be -1.

We will be discussing two different approaches. In the first method, we traverse the string from left to right and initialize the first index of every character as -1. If we encounter a character that is repeated, we compare its first or leftmost index with the current result and update the result if the result is greater.

C++ program to find the first repeated character in a string

Below is the C++ code:

#include <bits/stdc++.h> 
using namespace std; 
#define NUMBER_OF_CHARS 256 
  
int leftmost(string& str) 
{ 
  
    int firstIndex[NUMBER_OF_CHARS]; 
    for (int i = 0; i < NUMBER_OF_CHARS; i++) 
        firstIndex[i] = -1; 
    int result = INT_MAX; 
    for (int i = 0; i < str.length(); i++) { 
        if (firstIndex[str[i]] == -1) 
           firstIndex[str[i]] = i; 
        else
           result = min(result, firstIndex[str[i]]); 
    } 
  
    return (result == INT_MAX) ? -1 : result; 
} 
  
int main() 
{ 
    string str = "abbcc"; 
    int left = leftmost(str); 
    if (left == -1) 
        printf("All characters are distinct or string is empty ");
    else
        printf(" The first repeating character"
               " is %c", 
               str[left]); 
    return 0; 
} 

Output:

The first repeating character is b.

 

Time Complexity of the above solution is O(n).

Second method:

In the second method, we traverse the string from right to left and keep a track of the visited characters. If we encounter a character that is repeated, we update the result.

 

Implementation using C++:

The C++ code is written below:

#include <bits/stdc++.h> 
using namespace std; 
#define NUMBER_OF_CHARS 256 
  
int leftmost(string& str) 
{ 
    bool visited[NUMBER_OF_CHARS]; 
    for (int i = 0; i < NUMBER_OF_CHARS; i++) 
        visited[i] = false; 

    int result = -1; 
    for (int i = str.length() - 1; i >= 0; i--) { 
        if (visited[str[i]] == false) 
            visited[str[i]] = true; 
        else
            result = i; 
    } 
  
    return result; 
} 
 
int main() 
{ 
    string str = "abbcc"; 
    int result = leftmost(str); 
    if (result == -1) 
        printf("All characters are distinct or string is empty");
               
    else
        printf("The first repeating character is %c",str[result]);
    return 0; 
} 

 

Output:

The first repeating character is b

 

The second approach does fewer comparisons and is thus more efficient than the first approach.

Thank you for reading. I hope this helps.

 

Leave a Reply

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