Given a paragraph of text, and a list of k words, write a program to find the first shortest sub-segment that contains each of the given k words at least once. The length of a segment is the number of words included. A segment is said to be shorter than another if it contains less words than the other structure.

  • Ignore characters other than [a-z][A-Z] in the text.
  • Comparison between the strings should be case-insensitive.

Input format : The first line of the input contains the text. The next line contains k, the number of words given to be searched. Each of the next k lines contains a word.

Output format : Print first shortest sub-segment that contains given k words , ignore special characters, numbers. If no sub-segment is found it should return “NO SUBSEGMENT FOUND”

Sample Input : This is a test. This is a programming test. This is a programming test in any language. 4 this a test programming

Sample Output : a programming test This

Explanation : In this test case segment "a programming test. This" contains given four words. You have to print without special characters, numbers so output is "a programming test This". Another segment "This is a programming test." also contains given four words but have more number of words.

Constraints: Total number of characters in a paragraph will not be more than 200,000. 0 < k <= no. of words in paragraph. 0 < Each word length < 15

This question is asked in "Amazon" contest Winning Criteria : Best optimized code


closed as off-topic by ProgramFOX, Peter Taylor, Howard, Vereos, ace Feb 12 '14 at 16:12

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – ProgramFOX, Peter Taylor, Howard
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    \$\begingroup\$ What's the winning criterion? Why the limit to those 5 languages? Is this homework or an interview question? \$\endgroup\$ – Gareth Feb 12 '14 at 12:36
  • 3
    \$\begingroup\$ why theses tags ? it it restricted to these languages specifically ? \$\endgroup\$ – user16229 Feb 12 '14 at 12:36
  • \$\begingroup\$ @Gareth It is the coding challenge competition \$\endgroup\$ – nawazlj Feb 12 '14 at 16:12
  • \$\begingroup\$ @BenH yes, we have to solve by using this languages only... \$\endgroup\$ – nawazlj Feb 12 '14 at 16:13
  • 1
    \$\begingroup\$ How are you going to check which code is the best optimized? \$\endgroup\$ – ProgramFOX Feb 12 '14 at 16:58

Browse other questions tagged or ask your own question.