You are given a C++ string consisting of any lowercase alphanumeric characters ('a'-'z', '0'-'9') of length L > 2 (where L is even). One of the characters occurs L/2 number of times. The other characters are all different. For this problem, do not use any existing find or search string functions. Write a function that find this one character that occurs L/2 number of times in the input string:

char findHalfDuplicate(string s);

For example:

"1a2a3a4a"; // L = 8; 'a' occurs 4 times; the other characters are all different "a2a3a1"; // L = 6; 'a' occurs 3 times; the other characters are all different "2aa3"; // L = 4; 'a' occurs 2 times; the other characters are all different

Not valid input:

"1a"; // L has to be > 2 "z"; // L has to be even