A search page highlights keywords inside the words of a query. You get a sentence s (words separated by single spaces, no leading or trailing space) and a list of keywords elements.
Implement wrap_words(s: str, elements: list[str]) -> str. Handle each word on its own:
- Find the first occurrence of any keyword inside the word: the one with the smallest start index. If several keywords start at that index, take the longest one.
- Put
[before it and]after it. Only that one occurrence is bracketed, even if other keywords appear later in the word. - A word containing no keyword is left unchanged.
Return the words joined back with single spaces. Matching is case-sensitive, keywords are non-empty and may repeat in elements, and a keyword never spans two words.
wrap_words("banana split", ["an", "nan", "lit"])
# "b[an]ana sp[lit]" "an" starts at index 1, before "nan" at index 2
wrap_words("seesaw", ["s", "see", "saw"])
# "[see]saw" "s" and "see" both start at 0: the longer wins
wrap_words("hello world", ["xyz"])
# "hello world"
wrap_words("", ["a"])
# ""
Sentences can hold 20,000 words and elements 5,000 keywords of length at most 20. Checking every keyword against every word is too slow: aim for about O(total length of s × longest keyword).
Show hint
Put the keywords in a trie. For each start index of a word, walk the trie along the word and remember the deepest node that ends a keyword; the first start index with any match is your answer.