Bracket substrings matching any pattern
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given a sentence `s` (words separated by single spaces) and a list of strings `patterns`.
For **each word** in the sentence, if the word contains **any** pattern as a contiguous substring, wrap the matched substring in square brackets `[` and `]`.
- If a word contains **multiple** possible matches (different patterns and/or different positions), choose the match with the **smallest start index** (leftmost occurrence).
- If there is still a tie (same start index), choose the **longest** matching pattern.
- If a word contains **no** pattern, leave it unchanged.
- Matching is **case-sensitive**.
Return the transformed sentence.
## Example
- Input: `s = "hello uber"`, `patterns = ["ll", "ub"]`
- Output: `"he[ll]o [ub]er"`
## Constraints (reasonable interview assumptions)
- `1 <= len(s) <= 10^5`
- `1 <= len(patterns) <= 10^4`
- Total length of all patterns `<= 10^5`
- Words contain only printable non-space characters.
## Function signature (language-agnostic)
`transform(s: string, patterns: list[string]) -> string`
Quick Answer: This question evaluates string manipulation and pattern-matching competency, including substring search, prioritization rules for leftmost and longest matches, and handling of edge cases.
For each word, bracket the leftmost substring matching any pattern; ties use the longest pattern.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('hello uber', ['ll','ub'])
Expected Output: 'he[ll]o [ub]er'
Explanation: Prompt example.
Input: ('abcdef', ['bc','bcd','de'])
Expected Output: 'a[bcd]ef'
Explanation: Tie start chooses longest.
Input: ('NoMatch', ['x'])
Expected Output: 'NoMatch'
Explanation: No pattern.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.