Capitalize Matching Substrings | Dataford Interview Questions

The Uber Drivers app receives text containing driver-facing labels and messages. Given a text string and an array of target substrings, find every occurrence of each target and capitalize its first character while preserving the remaining characters.

When matches overlap, apply these rules: process the text from left to right, choose the longest matching target at the current position, replace it, then continue after the replacement. Matching is case-sensitive. Duplicate targets should behave like one target. Empty targets are not included.

Formal Specification

Implement capitalize_substrings(text, patterns).

Input: text, a string of ASCII letters, digits, spaces, and punctuation; patterns, an array of non-empty ASCII strings.
Output: A string with selected non-overlapping occurrences transformed so their first character is uppercase. The rest of each matched substring remains unchanged.

Constraints

1 <= len(text) <= 10^5
1 <= len(patterns) <= 10^4
The total number of characters across all patterns is at most 10^5
Every pattern is non-empty
All input characters are ASCII
Matching is case-sensitive

Function Signature

def capitalize_substrings(text, patterns):

Your question is Capitalize Matching Substrings. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem