How to Find the First Repeating Character in a String in C++

1. Find First Repeating Character in a String in C++
2. Use Hashing Technique to Find the First Repeating Character in a String in C++
3. Use Brute-Force Method to Find the First Repeating Character in a String in C++

In this tutorial, you’ll learn how to find the first repeating character in a string in C++. You will learn three approaches to fulfill this purpose: the hashing technique, the brute-force method, and the writing of your algorithm.

Find First Repeating Character in a String in C++

There are two approaches to attempt writing your algorithms; the first one is by traversing the string from left to right, and the second approach is by traversing the string from right to left and keeping track of the visited characters. The second approach is superior in performance to any other because it is more efficient by doing fewer comparisons.

Sorting algorithms can help you find the first repeating character in a string in O(n Log n) time. However, you can loop through the string and hash the characters using ASCII codes, run the loop on the hash array, and find the minimum position of any repeated character.

Code Example:

#include <iostream>

using namespace std;

#define numberChar 256

// left most string
int farLeftStr(string& primeStr) {
  // represents the first index
  int IndexNum[numberChar];

  for (int i = 0; i < numberChar; i++) IndexNum[i] = -1;

  // represents the resultIndexNum
  int resultStr = INT_MAX;

  for (int i = 0; i < primeStr.length(); i++) {
    if (IndexNum[primeStr[i]] == -1)
      IndexNum[primeStr[i]] = i;
    else
      resultStr = min(resultStr, IndexNum[primeStr[i]]);
  }
  return (resultStr == INT_MAX) ? -1 : resultStr;
}

int main() {
  string primeStr = "HouseOfTheDragons";
  int left = farLeftStr(primeStr);

  if (left == -1)
    cout << "All characters are distinct or string is empty ";
  else
    cout << "The first repeating character is: " << primeStr[left];
  return 0;
}

Output:

The first repeating character is: o

Traversing a string from left to right is doable regarding initializing the first index of every character as -1. You can compare the first or leftmost index of a repeated character (in case you encounter it) with the current result.

Furthermore, you can use O(N²) complexity to solve this problem by studying each character and searching for the same in the rest of the string.

Use Hashing Technique to Find the First Repeating Character in a String in C++

A Count array can find the first repeating character and keep a count of repeated characters in a string.

The hashing technique consists of four primary steps.

1. Creating one hash table.
2. Scanning characters.
3. Insert a character in the hash table if it’s not present.
4. Otherwise, returning that character as a duplicate.

Code Example:

#include <iostream>

// hashing function object type
#include <unordered_set>

using namespace std;

char getRepeatingChar(string &str) {
  unordered_set<char> hashObj;

  for (int i = 0; i < str.length(); i++) {
    char repChar = str[i];
    if (hashObj.find(repChar) != hashObj.end())
      return repChar;
    else
      hashObj.insert(repChar);
  }
  return '\0';
}

int main() {
  string expStr = "GameOfThrones";
  cout << "The first repeating character is: " << getRepeatingChar(expStr);
}

Output:

The first repeating character is: e

Another famous variation of this problem is printing the first unique or non-repeating character in a string by printing the results if the Count is equal to one. It’s possible to print all the repeating characters in a string as an extended variation to the original technique, but it’s not as straightforward as the basic hashing method.

As it is required for the user to create the Count array, the time complexity of this method will be O(n). In the worst case, with no repetition and extra space, its time complexity will be O(1).

Use Brute-Force Method to Find the First Repeating Character in a String in C++

It’s a simple method that enables programmers to check each character of a string to find a repeating character and output the corresponding results. If the end string is reached or the last character is scanned, no repeating character is found, and there’s no repeating character by default.

In the worst-case scenario, its time complexity is O(n2) in case of no repetition, and in best case scenario, it is O(1), which represents the presence of a repeating character at the second position. As you need a count array that takes a constant amount of memory, it’s more than the brute-force method, and the total extra space it takes is O(1), i.e., constant.

Code Example:

#include <iostream>

using namespace std;

int main() {
  string expStr = "Hello World!";
  string primeExp = "";

  // check the boundary of the `expStr` string
  if (expStr == primeExp) {
    cout << "The string is empty!";
  }

  for (int a = 0; expStr[a] != '\0'; a++) {
    for (int b = a + 1; expStr[b] != '\0'; b++) {
      if (expStr[a] == expStr[b]) {
        cout << "The first repeating character is: " << expStr[a];
      }
      break;
    }
  }
}

Output:

The first repeating character is: l