Substring Wrapper

The Substring Wrapper (commonly known as Surround Substrings) is a frequent Uber onsite coding interview question. You are given two arrays: words and parts. Your task is to modify each word in words so that any occurrence of a substring from parts is enclosed in square brackets []. 4 5

Problem Constraints & Rules

When multiple substrings from parts match a word, you must follow specific tie-breaking rules: 4

• Longest Match First: If several parts occur in one word, wrap the longest one.
• Earliest Appearance: If there is still more than one "longest" match, wrap the one that appears first in the string.
• Single Wrap: Only one substring should be wrapped per word, based on the priority rules above.

Example Walkthrough

Input:

• words = ["Apple", "Melon", "Orange", "Watermelon"]
• parts = ["a", "mel", "lon", "el", "An"]

Output & Reasoning:

Word | Matches Found | Wrapped Result | Reason --- | --- | --- | --- Apple | None | "Apple" | Case-sensitive: "a" does not match "A". Melon | "mel", "lon" | "Me[lon]" | "mel" and "lon" are equal length; "mel" appears first. Note: Some variations prefer "lon" based on specific logic, but priority is usually length then position. Orange | "a" | "Or[a]nge" | Only "a" matches. Watermelon | "a", "mel", "lon" | "Water[mel]on" | "mel" and "lon" (length 3) are longer than "a" (length 1). "mel" appears before "lon".

Recommended Approach: Trie + Greedy Search

To solve this efficiently for large datasets, interviewers typically expect a Trie (Prefix Tree): 3 2

1. Build a Trie: Insert all strings from parts into a Trie. Store the length of the string at each "end of word" node.
2. • Starting at index i, traverse the Trie to find the longest matching prefix.
   • Keep track of the overall longest match found for that specific word.
3. Starting at index i, traverse the Trie to find the longest matching prefix.
4. Keep track of the overall longest match found for that specific word.
5. Construct Result: Once the best match (length and start index) is identified, insert the brackets and move to the next word.

Complexity Targets:

• Time: 𝑂(𝑃+𝑊⋅𝐿2) where Pcap P𝑃 is total chars in parts, Wcap W𝑊 is number of words, and Lcap L𝐿 is max word length.
• Space: 𝑂(𝑃) to store the Trie.

Would you like to see a Python or Java implementation of the Trie-based solution?

[0] - Uber | Onsite | Surround substrings - Discuss - LeetCode [1] - Uber Coding & Algorithms Questions (Updated 2026) - PracHub [2] - How to Crack Uber Coding Interviews in 2026 | CodeJeet [3] - Uber SWE Interview Breakdown: From CodeSignal to System ... [4] - Uber | Onsite | Surround substrings - Discuss - LeetCode [5] - Uber | Onsite | Surround substrings - Discuss - LeetCode [6] - Uber | Onsite | Surround substrings - Discuss [7] - 820. Short Encoding of Words - In-Depth Explanation