Find First Repeated Character In A String

Let's start by understanding the problem statement for this task.

You are given a string of characters, your work is to find the first repeating character in the string.

Hint:

For finding the first repeating character in a string we can make use of the hashing technique where we will keep inserting the character if it is not present in the HashSet form before otherwise if it is present then we will print out the character which is a much-optimized solution rather than checking for each and every element in the array.

Quick Think:

For designing the above algorithm we have to use a hashset and keep the following things in our mind such as:-

• Every time we insert the character into the hashset we will check if the current character is there or not in the hashset, if yes then print out the character else insert the character in the HashSet and continue.

Algorithm:

Create a function which will be used to check is the current character is present in the hashset or not, with arguments as the string and it’s length.

Now follow the following steps to reach the solution:-

Step1: Define an unordered set and start traversing through the string.

Step2: Now, check if the current character is present in the unordered set to print the character, else go to step 3.

Step3: Insert the character into the unordered set.

Implementation Of The Above Algorithm:

Now let's see the implementation of the above algorithm,

#include <bits/stdc++.h>
using namespace std;
/*Function to find the first repeating character in the string. */
char repeating(string & str)
{
	unordered_set<char> set;
	for (int i = 0; i < str.length(); i++)
	{
		char d = str[i];
		/*If present return. */
		if (set.find(d) != set.end())
		{
			return d;
		}
		else
			set.insert(d);
	}

	return '\0';
}

/*Driver function to test above algorithm. */
int main()
{
	string str = "HELLO";
	cout << repeating(str) << endl;
	return 0;
}

The time complexity of the above algorithm is O(n).

The output of the above algorithm is L.

Explanation Of The Above Algorithm:

Let us take an example of the string as shown in the diagram above, to reach the correct output we need to follow the following steps:-

• The first letter of the word is “H”, and since it is not present in the unordered set, so we will insert the letter “H” into the unordered set as shown in the diagram above.

• Next, we see the letter “E” is also not present in the unordered set and so, we insert the letter “E” into the unordered set as shown in the diagram above.

• Next, we come across the letter “L” is also not present in the unordered set and so, we insert the letter “L” into the unordered set as shown in the diagram above.

• Again, we come across the letter “L”, since this time we see that the letter “L” is already present in the unordered set and hence, we output the result as shown in the diagram above.