FastPrep
Problem · String

Minimum Window of Required Words

Learn this problem
● MediumSalesforce logoSalesforceFULLTIMEPHONE SCREEN
See Salesforce hiring insights

Problem statement

Given a space-separated string text and an array requiredWords, return the shortest contiguous sequence of words that contains every required occurrence.

If a word appears multiple times in requiredWords, the returned window must contain it at least that many times. If several windows have the same minimum length, return the earliest one. If no qualifying window exists, return the empty string.

Function

minimumRequiredWordWindow(text: String, requiredWords: String[]) → String

Examples

Example 1

text = "the quick brown fox jumps over the lazy dog"requiredWords = ["fox","dog"]return = "fox jumps over the lazy dog"

The only window containing both required words starts at fox and ends at dog.

Example 2

text = "a b a c b a"requiredWords = ["a","a","b"]return = "a b a"

The first three words contain two occurrences of a and one of b. No two-word window can satisfy the multiplicities.

Constraints

  • 1 <= text.length <= 200000
  • text contains lowercase English words separated by exactly one space.
  • 1 <= requiredWords.length <= 20000
  • Every required word is a non-empty lowercase English word.
  • Matching is case-sensitive.

More Salesforce problems

drafts saved locally
public String minimumRequiredWordWindow(String text, String[] requiredWords) {
    // Write your code here.
}
text"the quick brown fox jumps over the lazy dog"
requiredWords["fox","dog"]
expected"fox jumps over the lazy dog"
checking account