UVa 11860: How to use Heap to solve it

Question

I am trying to solve a programming problem in UVa online judge:

Uva 11860 Document Analyzer

The problem setter of this problem wrote an tutorial on heap and some operation on it including insertion, deletion of node and mentioned at the end of that article - this problem can be solved by using heap. There might be other ways to solve it But I can't figure out how this problem can be designed to be solved using heap. I know how to code a heap in C++ and can define insert(), remove(), print() functions and some other operations like finding minimum item etc.

How this problem is related to heap?

Answer 1

The approach that comes to mind:

Have an (initially empty) heap of objects containing a word and its position - order this heap by the position.

smallestDistance = infinity
biggestSize = 0
for each word in the input:
   heap.insert(Pair(current position, word))
   hashMap[word] = current position

   // We saw the word after this occurrence, so remove it
   while hashMap[heap.minimum.word] != heap.minimum.position
     heap.pop()

   // We found another word!
   //   The previous smallest is invalid, since it doesn't contain this word
   if heap.size > biggestSize
     smallestDistance = currentPosition - heap.minimum
     biggestSize = heap.size
   // Is this distance better than the best so far? If so, use it instead
   else
     smallestDistance = min(smallestDistance, currentPosition - heap.minimum)
output smallestDistance