how to get the nearest char in a string

[misserwell]

a question.
how to get the nearest char in string , eg. there is a string is :
"abcdefdegfgh", then we should get the 'g' , because the it's distance is 2, and 'e' is 3 , 'f' is 4

I have tried to code as below :
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
char nearest(std::vector<char> _vect, int& _index, int& dist)
{
if ( _vect.size() <=2)
return '0';
typedef std::vector<char>::iterator iter;
iter it = _vect.begin();
iter move = _vect.begin();
iter result = move;
std::size_t tmp = _vect.size();
int index = 0;
while ( move != _vect.end())
{
std::size_t cnt = std::count(_vect.begin(), _vect.end(), *move);
int tmp_cnt = 0;
it = move;
while (tmp_cnt != static_cast<int>(cnt))
{
iter next = std::find(it + 1, _vect.end(), *it);
if ( next != _vect.end() && std::distance(it, next) < tmp)
tmp =std::distance(it, next);
++tmp_cnt;
it = next;

}
result = it;
++index;

++move;
}
dist = tmp;
_index = index;
return *result;
}

int main()
{
std::vector<char> vect;
vect.push_back('a');
vect.push_back('b');
vect.push_back('c');
vect.push_back('d');
vect.push_back('e');
vect.push_back('d');
vect.push_back('f');
vect.push_back('a');
int index = 0;
int &loc =index;
int disc = 0;
int &len = disc;
char val = nearest(vect, loc, len );
std::cout<<"Nearest char is "<<val<<std::endl<<"Index is "<<loc<<std::endl<<"Disc is "<<len<<std::endl;
}

I have used "abcdedfa" to test, but it is disappointed , I can the nearest right distant - 2 , but I can not get the right char(d) , anybody may help me , thanks in advance

[h9uest]

Good choice of data structure in the task can reduce your work and hopefully eliminate unnecessary bugs. In fact, the first data structure occured to me was a hash table of {char, position}. It will give you O(n) time complexity, where n is the length of the string.

In addition, it's quite easy to implement:

distance = some large number
for ith char in the string
     if char is not in hash_map
        insert char into hash_map
     else
        if (distance > i - hash_map[char])
            update distance
     endif
endfor

return distance

Think more about it, I'm sure you'll come up with a faster and easier solution. Good luck.

[misserwell]

h9uest , thank you very much , I got , I will review hash table firstly .