Oh, sorry about that. I think small modification of my code is needed to accommodate it. Yeah you are right Map can be useful, but I just want to make it happen in a single iteration.

/** * Returns the index of first non repeated character in a string * @param str * @return the index of first char that isn't repeated in the string, -1 for error and not found. * @throws */ public int firstNonRepeatedChar(String str) { boolean isRepeated = false; // Error check if(str==null || str.equalsIgnoreCase("")) return -1; // 0th and 1st char different case if(str.charAt(0)!=str.charAt(1)) return 0; for(int i=1;i

The question might be to look for the index of the first duplicate character instead. Because I think it will be very easy to find the first non-duplicate character. To look for the first non-duplicate character will be to simply get the first char, loop, then compare if each character in the string is equal to the first char. If it the comparison succeeds, you will immediately return the index. Else, return -1.

Making a few assumptions: Only going to see a known and relatively small (100ish) number of unique characters at most, nothing outlandish like a string that's miles long, etc. Track character counts using an array. Keep a queue of Pair objects that tracks characters seen only once and the index they were first seen at. Scan the string one character at a time, starting at index 0. Increment the count for that character. If incrementing to 1, add a new pair to the queue marking where that character was first encountered. If incrementing to 2, scan the queue and remove the pair for that character. When you're done, the first pair in the queue contains the first-encountered unrepeated character in the string. Could also track the number of repeated characters (incrementing that count when an individual character count hits 2) and terminate when all characters have been repeated. Should work well for small possible character sets (eg alphanumeric+punctuation). Scanning the queue when removing characters won't take too long (and isn't necessary when adding since we only add once at count=1). A palindrome containing each possible character twice yields the worst performance from this part; O(n^2), but for a small character set (small n), this isn't necessarily a big deal.

Ok, but one iteration would have to consume more memory which can be critical for a very large data set. It's the classic trade off between speed and memory. Even to perform 2 iterations would be constant time. Like I said, there's a trade-off.

@jjangu, notice that the question says "find the index" not "find the character". I would use a Map to keep track of the character count and the index, so we can later retrieve it.