Use an array count[26][2].
Here first col of each row represents the position of first instance of the
alphabet,if any, else -1.
and second col of each row represents the position of last repeated
instance of the alphabet, if any, else -1.
Now traverse the count array to find the row having both values positive.Of
all these rows,the the row having minimum count[i][0] can be found in
linear time .
The alphabet corresponding to that position is the answer.
Algo :-
int count[26][2].
initialise each element of count to -1.
Now, start from pos 0 and
for each char c at position pos in the string
if ( count[c-'a'][0] == -1)
count[ c- 'a' ][0] = pos;
else
count[ c- 'a' ][1] = pos;
int first_repeating_pos = INT_MAX;
for(int i=0;i<26;i++)
if( count[i][0] >=0 && count[i][1] >=0)
if(count[i][0] < first_repeating_pos)
first_repeating_pos = count[i][0];
--
Navin Kumar Gupta
Final Year,B.Tech(Hons.)
Computer Science & Engg.
National Institute of Technology,Jamshedpur
Mobile - (+91)8285303045
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/l_FbUt4SBSIJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
