Repeated Character Whose First Appearance is Leftmost

Given a string, find the repeated character present first in the string.

Examples:


Input  : geeksforgeeks
Output : g
(mind that it will be g, not e.)

Input  : abcdabcd
Output : a

Input  : abcd
Output : -1
No character repeats

Asked in: Goldman Sachs internship

We have discussed different approaches in Find repeated character present first in a string.

How to solve this problem using one traversal of input string?

Method 1 (Traversing from Left to Right) We traverse the string from left to right. We keep track of the leftmost index of every character. If a character repeats, we compare its leftmsot index with current result and update the result if result is greater

#include <bits/stdc++.h>

using namespace std;

#define NO_OF_CHARS 256

int firstRepeating(string& str)

{

int firstIndex[NO_OF_CHARS];

for (int i = 0; i < NO_OF_CHARS; i++)

firstIndex[i] = -1;

int res = INT_MAX;

for (int i = 0; i < str.length(); i++) {

if (firstIndex[str[i]] == -1)

firstIndex[str[i]] = i;

else

res = min(res, firstIndex[str[i]]);

}

return (res == INT_MAX) ? -1 : res;

}

int main()

{

string str = "geeksforgeeks";

int index = firstRepeating(str);

if (index == -1)

printf("Either all characters are "

"distinct or string is empty");

else

printf("First Repeating character"

" is %c",

str[index]);

return 0;

}

Output:


First Repeating character is g

Time Complexity : O(n). It does only one traversal of input string.
Auxiliary Space : O(1)

Method 2 (Traversing Right to Left) We traverse the string from right to left. We keep track of the visited characters. If a character repeats, we update the result.

#include <bits/stdc++.h>

using namespace std;

#define NO_OF_CHARS 256

int firstRepeating(string& str)

{

bool visited[NO_OF_CHARS];

for (int i = 0; i < NO_OF_CHARS; i++)

visited[i] = false;

int res = -1;

for (int i = str.length() - 1; i >= 0; i--) {

if (visited[str[i]] == false)

visited[str[i]] = true;

else

res = i;

}

return res;

}

int main()

{

string str = "geeksforgeeks";

int index = firstRepeating(str);

if (index == -1)

printf("Either all characters are "

"distinct or string is empty");

else

printf("First Repeating character"

" is %c",

str[index]);

return 0;

}

Output:


First Repeating character is g

Time Complexity : O(n). It does only one traversal of input string.
Auxiliary Space : O(1)

The method 2 is better than method 1 as it does fewer comparisons.

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to [email protected]. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please Improve this article if you find anything incorrect by clicking on the “Improve Article” button below.

Source link

Reader Interactions

Leave a Reply Cancel reply