[algogeeks] Re: What is the most efficient algorithm to find the first non repeating char in a string

[Alfredo Cruz]

Hi, yeah, in general I think that you already know the alphabet under which you are working. So, either you work with ASCII codes or Unicode codes so as Chitta said you maintain an array with your alphabet sorted by their codes. Then you start scanning your string and for each character you see you search for it in your codes array, you mark it as seen and save the index. If any time along your scanning you see it again you mark it as repeated. Then you scan your codes array and look for the smallest index. The whole process takes, if n is the length of the string: O(nlog(length(codes array))) for the scanning and O(length(codes_array)) for the answer. You can improve the last bound by using a Fib heap (for example) as a candidates heap, each time you see a char is repeated then you delete it from the heap, at the end you pop the min and you are done... I hope this helps Alfredo Cruz Hi, If the string contains only alphabets then we can maintain an array of 26 characters which tells that the alphabets has occured once or not....if it is already occured .....we can output it directly... more efficient algos are welcome On 8/8/07, JOE11790 <[EMAIL PROTECTED]> wrote: Hi, I got a question in the interview about how to find the first non repeating char in a string. For example for string ABCA, B is the first non repeating char. It is easy to come up with a brute force algorithm by scanning the string. But is there an efficient way to do it? thanks --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---