Bracket the first matching substring in each word

Implement wrap_substrings(s: str, elements: list[str]) -> str.

s is a sentence of words separated by single spaces. elements is a list of strings. For each word in s, find the first substring of that word that equals one of the elements and wrap it in square brackets. Leave words with no match unchanged, and keep the spaces between words as they are.

Rules for choosing the match in a word:

• Pick the match that starts at the smallest index in the word.
• If several elements match at that index, pick the longest one.
• Wrap only that one match; later matches in the same word are left alone.
• Matching is case-sensitive. Ignore empty strings in elements.

Constraints: 0 <= len(s) <= 10^5, 0 <= len(elements) <= 10^4, each element has at most 100 characters.

Example 1

s = "orange banana kiwi"
elements = ["an", "ana", "wi"]
output: "or[an]ge b[ana]na ki[wi]"

In banana, both an and ana start at index 1, so the longer ana is wrapped.

Example 2

s = "abc hello"
elements = ["c", "ab", "abc"]
output: "[abc] hello"

c also matches in abc, but ab and abc start earlier, and abc is the longer of those. hello has no match.

Start with a straightforward solution, then make it fast when there are many elements.

Reconstructed from the reported question; details may differ from what interviewers ask.