First non-repeated character

Question

Challenge description is here need to find the first non repeated character from the string:

Write a program which finds the first non-repeated character in a string.

Input sample:

The first argument is a path to a file. The file contains strings.

For example:

yellow
tooth

Output sample:

Print to stdout the first non-repeated character, one per line.

For example:

y
t

Please let me know can I improve my solution.

#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <cstring>

 
void findNonRepeatedChar( const std::string& record)
{
    auto pred= [&record] ( char a, char b){ 
                  return strchr( record.c_str(), a ) < strchr( record.c_str(), b ); 
                };
    std::map< char, int, decltype(pred) > stringMap(pred);
    for( auto elem : record )
    {
        auto it = stringMap.find( elem );
        if( it != std::end(stringMap) )
        {
            ++(it->second);
        }
        else
        {
            stringMap.insert( std::make_pair<char&,int>(elem, 1));
        }
    }
    for( auto elem : stringMap)
    {
        if(elem.second == 1)
        {
            std::cout<< elem.first << "\n";
            break;
        }
    }
}

void readInputFile( const char * fileName )
{
    std::ifstream inFile( fileName, std::ifstream::in );
    std::string record="tooth";
    
    if( !inFile.is_open())
    {
        std::cout<<"File open failed \n";
        return;
    }
    while( getline( inFile, record ) )
    {
        findNonRepeatedChar(record);
    }
}

int main( int argc, char* argv[] )
{
    if( argc < 2 )
    {
        std::cout<<"Usage:program_name input_file_name \n";
    }
    readInputFile(argv[1]);
}

Answer 1

I've reviewed your code and here's what I've found.

Reconsider your algorithm

It's not really necessary to iterate through all of the characters in the string, as the current code does. Since the task is to find only the first non-repeated character, the algorithm can terminate as soon as it finds a non-repeated character. A simple way to do that is this:

void findNonRepeatedChar( const std::string& record )
{
    for (std::string::size_type i = 0; i < record.size(); ++i) {
        if (record.rfind(record[i]) == i) {
            if (record.find(record[i]) == i) {
                std::cout << record[i] << '\n';
                return;
            }
        }
    }
}

Reconsider the interface

It is odd that a function named findNonRepeatedChar() does not actually return anything. The code could be clearer if it actually returned the non-repeated letter and left the printing to the calling routine.

Don't instantiate an object that is not needed

There is no reason to instantiate the record to "tooth" (or any other value) within readInputFile.

Use more descriptive function names

The function named readInputFile does more than simply read the file and as mentioned before, the findNonRepeatedChar() function doesn't return anything but prints as a side effect. I'd be inclined to omit readInputFile entirely, and put its contents within main and to change the interface to as previously mentioned.

Give the user useful help

The program is probably not really named program_name so the string that's printed if there aren't enough commmand line arguments should probably instead be:

std::cout << "Usage: " << argv[0] << " input_file_name\n";

Answer 2

Your findNonRepeatedChar function seems more complex than required. I disagree with the algorithm that @Edward posted, as it makes what should be a linear time solution into a quadratic time solution.

Here is a simpler algorithm:

• Build a map containing characters and the number of times they exist in the string.
• Walk through the string from left to right, looking up the number of times the character appears in the string.

In code, this looks like:

char find_first_non_repeat(const std::string& s)
{
    std::unordered_map<char, unsigned> count;
    for(auto c : s) {
        count[c] += 1;
    }
    for(auto c : s) {
        if(count[c] == 1) {
            return c;
        }
    }
    return char(0);
}

Here, I've used an unordered_map. Generally you should prefer unordered_map over map unless you absolutely need ordering.

It's easier to use operator[] here instead of dealing directly with iterators and comparing to end to decide whether to insert or not. For complex objects using operator[] can have performance penalties, but for basic types like characters and integers, this isn't a concern.

The interface is also different: it returns a char instead of just printing the character. This change might seem unimportant, but actually, it's a pretty big difference in at least one area: testing. Your function, as it stands, is very hard to test in any kind of automatic way. Having it return the value instead makes it easier to test (and also adheres better to the single responsibility principle).

Answer 3

Assuming we are speaking of bytes only. Not knowing what has to be done if no such character is found.

Here is a simple C version. No building, minimal scanning.

Let p a pointer to the first char of the string. Let n be the length of the string. The function returns the character in an int, or -1 if no such character exist.

static int non_repeat(const char* p, size_t n)
{
    const char* l = &p[n];

    while(p < l)
    {
        char c = *p;

        int n; // count the occurrences after the current one
        for(n = 0; (++p < l) && (*p == c); ++n);
        {
        }

        if(n == 0) // no repeat ?
        {
            return c;
        }
    }

    return -1; // nothing has been found
}