CareerCup

Store all the words in Trie data structure. Trie structure is

class Trie{
		HashMap<Character,Trie> book;
		int pageNum;
		Trie(int pageNum){
			book=new HashMap<>();
			this.pageNum=pageNum;
		}

}
or store each page in a trie. start from the page 1 and insert words into trie, if a repeated word exists we already have the page number of the same word which occurred first. Time complexit is (w1.length+w2.length)

@sivapraneethalli This is a good idea when the Book is a constant and the words are variable. My question is that for every request, we get a new book and two new words. For such a case, the space and time of storing the complete book in Trie would be large and also unnecessary task.

This problem seems simplified version of finding minimum distance between those 2 words. Here since we need to find distance between first occurrences, just start from start of book and maintain idx = -1. If we encounter any of word, store it's index and look for next word.

// convert book into list of words
int idx = -1;
for (int i  = 0; i < list.size(); i++) {
	if (list[i] == w1 || list[i] == w2) {
		if (idx != -1) {
			if (list[i] != list[idx])
				return i - idx;		
		}
		else
			idx = i;
	}
}
return -1; // no pair found