Finding the shortest sublist that contains all search terms

Question

I've been trying to get better at writing algorithms and came across a problem that was something like this:

Given a list of words:

search_list = ["this", "is", "an", "issue"]

Find the closest occurrences of all of these words in another list, and return the first occurrence and last occurrence:

given_list = ["this", "tv", "is", "an", "state", "node", "is", "this", "issue", "issue", "an"]

Given these two lists, the correct result would be [6, 10], because the closest occurrences of the search_list, would start with the "is" at index 6, and finish with "an", at index 10.

Having said that, here are more details:

closest occurrences - definition

closest occurrence is the smallest subset of given_list in which all of the words occur. By "smallest subset", I simply mean the smallest absolute difference between the smallest occurring index, and the largest occurring index.

allowed inputs

1) search_list - a list or set of words that will only contain unique words. Again, no repeating words will be in this input parameter. This is the set of words that will be used to search given_list to find the shortest/closest subset or occurrences of. 2) given_list - a list or array of words that may contain duplicate words. This is the list that we need to find the smallest/closest subset of search_list in.

expected output

Find the closest occurrences of all of these words in another list, and return the first occurrence and last occurrence.

Here is what I've tried so far: To start, I thought it'd be helpful to find all of the occurrences of each word.

def find_sub_list(search_list, given_list):
    result_list = []
    for value in search_list:
        inner_list = [i for i, val in enumerate(given_list) if val == value]
        result_list.append(inner_list)
    return result_list

Given the variables above, this would result in:

[[0, 7], [2, 6], [3, 10], [8, 9]]

From these results, the correct answer would be [6, 10], because 4 is the shortest distance in which the words occur. However, I can't seem to find a better way to find the closest occurrences without checking every possible outcome. Is there a particular data structure that would make this process faster?

Edit

To further define "closest occurrences", I'll give an example.

search_list = ["one", "two", "three"] given_list = ["one", "black", "two", "blue", "three", "green", "two", "three"]

The correct answer in this case would be [0, 4]. "two" and "three" occur at indices 6 and 7. However, "one" occurs at index 0, and "two" and "three"'s also occurs at 2 and 4. This subset with indices 0, 2, 4 is a smaller or closer subset than that of 0, 6, 7. Hopefully that makes more sense?

Other notes:

• search_list cannot have repeating words. Items must be unique.

Answer 1

Go over the list, and maintain the last occurrence of each word in the search list. Whenever you find a word in the search list, find the minimum last occurrence among all other words in the search list - this gives you a candidate closest occurrence, which you take note of if it's the best seen so far. In the end, return the best closest occurrence observed.

To execute this algorithm efficiently, you need an efficient array-like data structure which supports the following operations:

• Change the value of item $i$.
• Return the minimum value of all items other than item $i$.

When the search list is very short, you can just use an array. For large search lists, you can probably use a modified heap to support all of these operations in $O(\log m)$ time, where $m$ is the size of the search list. The end result is an $O(n\log m)$ algorithm, where $n$ is the size of the main list.

Answer 2

Here's a simple algorithm.

1. For each word $w$ in search_list,
   1. find the left-most occurrence of $w$ in given_list and label all entries to the right with $\leftarrow_w$, and
   2. find the right-most occurrence of $w$ in given_list and label all entries to the left of it with $\rightarrow_w$.
2. Find the right-most entry $l$ that is labelled with all $\rightarrow_w$.
3. Find the left-most entry $r$ that is labelled with all $\leftarrow_w$.

You can implement the labels as bitmask; assuming you can manipulate bits and compare the whole masks in constant time, this algorithm runs in time $\Theta(mn)$, with $n$ and $m$ be the number of elements in the two lists.