Finding the shortest sequence containing the keywords (Minimum window subsequence problem)

Problem

Find the shortest string [] containing the keyword inside

Example,

Words: sky cloud google search sky work blue
Keywords: sky blue
Return: sky work blue




Explanation

First of all, this is the same question as the "Finding the minimum sub-string" question. It was modified by using words instead of characters to fool the interviewees.

In the first attempt, I fell for this trick and thought I add to use a different approach such as binary search. The second attempt was not far from the first approach but still did not figure out the fact that it was another variation of the minimum sub-string sequence problem.

In the third attempt (a few months after the second attempt), I tried to simplify the word into just numbers and found that it was, indeed, a minimum sub-string sequence. I took the greedy approach to solve this problem in $O(N)$ time.

For a detailed explanation of the algorithm, you can refer to "Finding the minimum sub-string".


Key assumptions made in this solution are:

• keywords don't include the duplicate word
• the answer does not have to contain keywords in order.

UPDATE(2023-03-01): Solved the problem again and chose the wrong direction and spent 1 hr writing the wrong code (it worked but had bugs).

After understanding that it was a minimum span problem, rewrite the code and found that the original code had a bug. Fixed the bug.

Here is the new solution without a bug.

Here is the python solution. This code has lots of room for improvement if I had more time.



Practice statistics:

42:34 to write up the code without test cases (I should move faster next time) - yay!! I wrote the code in under 45 mins
06:04: to write up the test cases and refactor the code
03:41: debug the code. --> This should not happen next time. !!