Find the first nonrepeating character in a string?

[jsmith]

I like this one the best :)

Instead of using a hardcoded try count, you could take the lowest 24 bits of
the MD5 or SHA1 hash of the input string (perhaps concatenate with a
random string for a little extra uncertainty.)

[Duthomhas]

The count is irrelevant. See line 31. :-]

[jsmith]

Oh, oops, I completely misread the algorithm.

[Duthomhas]

Obfuscation at its best. (Or worst...) I'm sure it makes an argument for something... XD

[BettyBoopTS]

errr,, How bout them Red Sox?? <whistling while looking around at the sky>

[Duthomhas]

The algorithm in my last piece of code takes pains to randomly sample the data a large number of times (see the variable tries). This would normally increase the probability of getting the correct answer.

However, since any index found (which indexes a singleton character) is automatically saved in found, the result is simply the last randomly chosen index that selects a singleton character -- meaning that no matter how many tries you use, the result is still completely random.

That could be fixed by changing line 31 to read something like

    31       if (index < found) found = index;

Get it? Eh? Eh? :->

[olredixsis]

Well what if you want to get all the non-repeating characters.

Is this algorithm wrong? Thanks.

1. first get input from user
2. then store it in another string to erase some characters (step 5)?? <- is it recommended in professional programming not to pass the original string to another string?. sorry I'm still learning C++.

3. get the first character
4. using find method of algorithm class get the location of all same characters
5. if the character exists in another location. use erase method. else go to next character
6. repeat step 4 and 5 until it reaches the null character.

[BettyBoopTS]

Given a string "teeter", the first non repeating character would be 'r'.
in "toothless", it would be 'h'.

I'm wondering about the most efficient way to get this done?

that was the criteria

[Duthomhas]

Hmm, that was a good question olredixsis.

An important concept in CS is that of filters and predicates.
http://en.wikipedia.org/wiki/Filter_%28higher-order_function%29
http://en.wikipedia.org/wiki/Predicate_%28computer_programming%29

The only filter in the STL is the remove_copy_if() function, which gives you an extra something to wrap your brain around because it works with negative conditions instead of a straight-forward condition.

I have already given an example of a filter on lines 37-43 of my second post ( http://www.cplusplus.com/forum/beginner/17935/#msg91134 ). Here it is:

  // We are only interested in alphanumeric characters, so we'll populate our
  // counts using a copy of the user's input string where all unwanted
  // characters have been removed.
  remove_copy_if(
    s.begin(),
    s.end(),
    back_inserter( t ),
    not1( ptr_fun <int, int> ( isalnum ) )
    );

Basically what that says is: for each character in s (lines 5-6) that does not satisfy the predicate "i am not an alphanumeric number" (line 8), append it to t (line 7).

Take a look at the remove_copy_if() docs for another description of what it does.
http://www.cplusplus.com/reference/algorithm/remove_copy_if/


Back to the idea of filtering out characters that have repeats (leaving us with only those characters that are non-repeating), we can replace my filter example with the following:

  // Now find ALL characters in the original string whose count == 1
  string originals;
  remove_copy_if(
    t.begin(),
    t.end(),
    back_inserter( originals ),
    not1( bind1st( mem_fun( &count_t::match1 ), &counts ) )
    );
  cout << "The non-repeating alphanumeric characters are: \"" << originals << "\".\n";

This has the convenient feature that the algorithm remains O(n) (because of my count_t class).

Well, that's all from me for now...
Hope this helps.

[olredixsis]

I see. Thanks Duoas.