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).

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.