I think your idea is solid, although I may not have used a tree.
Basically, you have to remember every character you've encountered as you parse, then check each new one.
If we're simply talking about characters, I might just use an array of 256 ints. read a character, use it's ascii value as the index into the array. if the value there is 0, i have not encountered it, so I set the value to 1. If the value is 1, i've encountered it, so I'm done.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Himanshu, both your solutions are literally fine (they do not iterate over the array) but they have a hidden iteration in the other data structures - the TreeSet.add() and ArrayList.contains() method both perform iteration to look for the given element. The TreeSet.add() takes O(log n) time, the ArrayList.contains() takes O(n). So using an ArrayList is no better than iterating over the given char array - it's just as if you were copying it and iterating over the char copy. The TreeSet solution is nice and fast (fastest possible in the general case of object repetition), though Fred's solution is fastest possible in the bounded by character's values case. See Wikipedia.
Write a method that finds the index of the first repeating character in an array, by iterating through the array only once. If there is no repeating character, the method should return -1.
You are not allowed to use a inner loop like
because that would iterate through the array more than once.
(Hint: Data structures from the Collections framework can be used to avoid a nested loop)
Joined: Feb 18, 2008
Judging from the hint, I'd say that the solution with set is the most suitable - fulfils the task's requirements, is fast enough and memory -optimal. You may consider using HashSet instead of a TheeSet initialized to the array's capacity - the add() operation will be even faster. The solution with the int array is smart, but for small char arrays a lot of memory will be wasted.