FastPrep
Problem · Array

Highlighted Context Windows

Learn this problem
● MediumAnduril logoAndurilFULLTIMEONSITE INTERVIEW

Problem statement

Given an ordered array of words, a non-empty literal target, and a nonnegative context width, find every word containing at least one case-sensitive occurrence of target. Each matching word creates an inclusive source-index window containing that word and up to context whole words on each side, clipped to the array bounds.

Merge windows that overlap or touch. Return the merged windows in increasing source order. Inside every returned word, wrap every non-overlapping occurrence of target with the literal marker **; leave nonmatching words unchanged.

Function

highlightContextWindows(words: String[], target: String, context: int) → String[][]

Examples

Example 1

words = ["alpha","catapult","beta","scatter","gamma"]target = "cat"context = 1return = [["alpha","**cat**apult","beta","s**cat**ter","gamma"]]

The match windows are indices 0 through 2 and 2 through 4. They overlap at index 2, so they form one returned window.

Example 2

words = ["aaaa","x","aa"]target = "aa"context = 0return = [["**aa****aa**"],["**aa**"]]

With zero context, the separated matching words remain separate windows. Matching proceeds left to right using non-overlapping occurrences.

Constraints

  • 0 <= words.length <= 100000.
  • 0 <= words[i].length <= 1000 and the total number of characters is at most 300000.
  • 1 <= target.length <= 1000.
  • 0 <= context <= words.length + 1000.
  • The literal marker ** does not occur in any input word or in target.

More Anduril problems

drafts saved locally
public String[][] highlightContextWindows(String[] words, String target, int context) {
    // Write your code here.
}
words["alpha","catapult","beta","scatter","gamma"]
target"cat"
context1
expected[["alpha", "**cat**apult", "beta", "s**cat**ter", "gamma"]]
checking account