# Implement placeholder-based pattern matcher You are given: 1. A string `s` that may contain **placeholders** delimited by the `%` character. 2. A dictionary `dict` mapping keys (strings) to replacement values (strings). A **placeholder** is any substring that starts and ends with `%`, for example `%key%`. The text between the two `%` characters (here, `key`) is used as a lookup key in `dict`. Example: - `s = "a%sd%fasd%dog%sdfisan"` - `dict = { "sd": "HELLO", "dog": "CAT" }` Expected output: - `"aHELLOfasdCATsdfisan"` ### Rules - Parse `s` from left to right. - Text outside of `%...%` is copied directly to the output. - When you encounter a `%`, you start reading a key until the next `%`: - The characters between the two `%` characters form the key. - Look up this key in `dict`. - If the key exists, append `dict[key]` to the output. - If the key does **not** exist in `dict`, the function should report an **error** (for example, by returning a special error value or throwing an exception; define your choice clearly in your solution). - You may assume that `%` characters are properly paired (no unmatched `%`). - There is no escaping mechanism for `%` (every `%` starts or ends a placeholder). ### Task - Implement a function that performs this substitution according to the rules above. - Clearly specify: - The function signature in the programming language of your choice. - How errors are represented/returned when a key is missing from `dict`. - Aim for a solution that runs in linear time in the length of `s` (plus the cost of dictionary lookups). ### Constraints & Assumptions - Preserve the scope, facts, inputs, and requested outputs from the prompt above. - If the prompt leaves a detail unspecified, state a reasonable assumption before relying on it. - Keep the answer interview-ready: concise enough to present, but concrete enough to implement or evaluate. ### Clarifying Questions to Ask - Clarify input sizes, value ranges, mutability, return format, and tie-breaking. - State the target time and space complexity before coding. - Call out edge cases such as empty inputs, duplicates, invalid values, overflow, and boundary sizes. ### What a Strong Answer Covers - A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it. - A correctness argument that explains why the algorithm covers all required cases. - Time and space complexity, plus at least one alternative approach when relevant. - Focused tests for normal cases, edge cases, and failure modes. ### Follow-up Questions - How would the approach change if the input were streaming or too large for memory? - What invariants would you assert in production code? - Which tests would catch off-by-one, duplicate, or tie-breaking bugs?