@Sravanreddy: Filling in a few details: Find the first occurrence of each given word in the document. While doing this, insert the location of each word into a min-heap, and keep track of the maximum of all locations. Record the difference between the top of the heap and the maximum as the smallest segment so far.
Execute the following loop: Find the next occurrence of the word at the top of the heap. If there is none, break out of the loop. The smallest segment you have found so far is the answer. Otherwise, replace the top of the heap with the new location and restore the heap condition. Update the smallest segment so far if the difference between the (new) top of the heap and the maximum is better. This algorithm is O(n k log k) in time and O(k) in space. I don't see how you can do it in O(n log k). Dave On Dec 1, 3:39 pm, sravanreddy001 <sravanreddy...@gmail.com> wrote: > An idea is to start with a heap of size k. > Its tricky how to keep track of the start and end indices of the smallest > length. Do not enter a duplicate element in the heap. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
