Finding the first non-repeating character in a string Below is a problem I encountered during an online course. There are a lot of similar questions asked on this, but I couldn't find a solution there as well as I believe my specific issue is a bit different from the rest.


  Given a string s, find the first non-repeating character in the string
  If there is no such character print ‘@’.  You are required to complete the function
  
  Input Format:    String s
  
  Output Format: First non-repeating character or @
  
  You are supposed to implement char 
  char FirstNonRepeatedchar(char* str, int len): which takes a pointer to input string str and length of the string(including ‘\0’). The function should return either the first non repeating character or ‘@’
  
  Input Constraint: All input characters will be either lower or upper case english alphabets. 

   str[i]  [a,z][A,Z]

  
  There will not be any space in the input string.


 /************ Prefix Code Begins*******************/
 #include &lt;iostream&gt;
 #include &lt;string&gt;
using namespace std;

//function finds the first non-repeating character
 char FirstNonRepeatedchar(const char* , int);

int main(){

int len;
string line;
getline (cin, line);

len = int(line.length());

cout &lt;&lt; FirstNonRepeatedchar(line.c_str(), len);


return 0;
}
/******************* Prefix Code Ends******************/


Also, note I cannot change anything in the prefix code above. I wrote 2 solutions: first one below is giving correct output.

char FirstNonRepeatedchar(const char* str, int len){
    int count[26]={0};
    for(int i=0;i&lt;len;i++)
    {
        count[*(str+i)]++;
    }
    for(int i=0;i&lt;len;i++)
    {
        if(count[*(str+i)]==1)
        return *(str+i);
    }
return '@';
} 


The above solution iterates the string twice. So, I tried to improve the complexity by implementing it using a hash.

char FirstNonRepeatedchar(const char* str, int len){
int count[26]={0};
int j;

char c;
if(isupper(*str)==1)
{ c='A';
}
else
c='a';
for(int i=0;i&lt;len;i++)
{   j=*(str+i)-c;
    if(count[j]&lt;0)
    ;
    else if(count[j]==0)
    count[j]=i+1;

    else if(count[j]&gt;0)
    count[j]=-i;

}
int min=len+1;
for(int i=0;i&lt;26;i++)
{   
    if(count[i]&gt;0 &amp;&amp; count[i]&lt;min)
    min=count[i];

}
if(min==len+1)  
return '@';
else
return *(str+min-1);
}


Is the second solution I gave the most optimized solution possible for this problem?
Let's try a solution that doesn't use an array with all the required bookkeeping.  The following code works, and bypasses the problems others have pointed out.

First, a quick template function that searches for duplicates given a char:

template &lt;typename T&gt;
inline bool repeated(char c, T first, T last) {
    size_t count = 0;
    while (first != last) {
        if (*first == c) ++count;
        if (count &gt; 1) return true;
        ++first;
    }
    return false;
}


Now we create a set of unique characters and then scan the string to see if there are any duplicates.  If there are, we remove the char from the set and continue to the next one.

char FirstNonRepeatedchar(const char* str, int len) {
    auto uniq = std::set&lt;char&gt;(str, str + len);
    auto first = str;
    auto last = str + len;
    while (first != last) {
        if (auto it = uniq.find(*first) != uniq.end()) {
            if (!repeated(*first, str, str + len)) return *first;
            uniq.erase(it);
        }
        ++first;
    }
    return '@';
}