Intro
When you search in google, it always shows you a result with a sample text from the found webpage.
For example if you search for "Madonna greatest vinyl", google will show you one line link, and below a short excerpt from that found webpage:
Madonna Greatest Hits Records, LPs, Vinyl and CDs
Madonna - Greatest Hits Volume 2, Madonna, Greatest Hits ... vinyl Is Fully Restored To As Near New Condition As Possible. Shipping & Multiple Order D..
Task
Imagine yourself you work for google and you have to write a program/function which takes in:
- a string containing many words (the webpage content)
- list of searched words (at least 3)
and returns the shortest excerpt of given string (webpage) containing all searched words.
Example
Given this webpage content:
This document describes Session Initiation Protocol (SIP), an application-layer control (signaling) protocol for creating, modifying, and terminating sessions with one or more participants. These sessions include Internet telephone calls, multimedia distribution, and multimedia conferences.
and these searched words:
calls, sessions, internet
the program should return:
sessions include Internet telephone calls, as this is the shortest substring containing all 3 searched words. Note that one more substring contains these 3 words, it is "sessions with one or more participants. These sessions include Internet telephone calls", but it is longer, so it was discarded.
Rules
- If the string is empty, return empty string
- If all searched words are not found in given string, return empty string
- Search is ignoring letters case
- At least 3 words need to be specified for searching
- The returned string may contain the searched words in different order than specified
Challenge
Write the fastest code. It's for google, right? Remember that repeatable strings comparison is very expensive.