For each possible word, we ask the question: What possible queries can lead to this word?. For example consider the word: abd. Below are the possible (prefix, suffix) queries that can return abd 1 2 3 4 5 6 7 8 9 10 (prefix, suffix) a abd a bd a d ab abd ab bd ab d abd abd abd bd abd d Now, given word.length <= 7. Each word can at maximum generate 7*7=49 such pairs. Can we store all of them in a hashmap? Yes, because the total storage = 49 * number of words = O(n) Which is acceptable for this problem. ...

This problem is very similar to lc543, which is about finding the longest edge path in a tree. You can just copy over that code, and add 2 lines in it. Here we are doing the same thing as in lc543, however, when we encounter a non-matching child. We treat it as null. For example, here the longest path at root node is highlighted below in red with 6 edges. ...

I keep track of the top k elements in sorted list. The kth largest element is the smallest of the top k elements. e.g. top k(=6) elements: [3,5,7,10,42,56] in sorted order. The kth largest element = 6th largest element = smallest element in above list. When I insert an element, I simply check if it can make it’s place among k largest elements already present in the list. Which it can, if it can defeat the smallest element in our list. ...

When numbers from $$\in$$ [0,n-1] are sorted in an array of size n. Their sorted position is equal to their index. Subset of numbers in array[i:j] can form a partition, if all elements in [i,j) are available in array[i:j]. For example [2,0,1] can form a partition, since they are at index 0, 1, 2 respectively. Sorted will involving swapping them at their correct position. The basic idea behind this solution is that we try to identify such partitions, where all elements required to be sorted in [i, j] are available in current partition. ...

For each word, we basically store all versions of it after removal of 1 character. For example, 1 2 3 4 5 6 hello -> ello -> removed h@0 hllo -> removed e@1 helo -> removed l@2 helo -> removed l@3 hell -> removed o@4 We can store: wordAfterRemoval,indexOfRemoval in hashmap. So whenever we search for a word like: hexlo then we can try removing it’s 2nd index and search: helo,2 in the map, which we will find. ...