Friday, January 17, 2014

Given a stream of characters, find the kth non-repeated character at any given time.

Solution:
- Use an array of size 256, and update the count of each characters as arrives
- Use another array of same size, to keep track of order of the characters appeared in the stream, update this stream only if count of that character is 0 in the first array before updating.

When you need to find the kth non-repeating character, start traversing the second array and get the count, You can get the kth character whose count is 1 in the first array

Leave a comment if solution is not clear!

Reactions:

1 comment: