Problem Description

You are tasked with implementing a placeholder-based pattern matcher. Given an input string s that may contain placeholders and a dictionary dict mapping keys to replacement values, your function should substitute all identified placeholders with their corresponding values from the dictionary.

A placeholder is defined as any substring within s that starts and ends with a % character. The text found between these two % characters serves as a lookup key in the provided dict.

Example

• s = "a%sd%fasd%dog%sdfisan"
• dict = { "sd": "HELLO", "dog": "CAT" }

Expected output: "aHELLOfasdCATsdfisan"

Requirements

• The input string s must be parsed from left to right.
• Any text outside of a %...% placeholder sequence should be copied directly to the output.
• Upon encountering an opening %, the parser should read characters until the next closing % to form a key.
• This key should then be looked up in dict.
  • If the key exists in dict, its corresponding value (dict[key]) must be appended to the output.
  • If the key does not exist in dict, the function must report an error. You are required to clearly define your chosen error reporting mechanism (e.g., returning a special error value, throwing an exception).
• You may assume that all % characters in s are properly paired; there will be no unmatched %.
• There is no escaping mechanism for the % character; every % encountered either starts or ends a placeholder.

Deliverables

• Implement a function that performs the described substitution.
• Clearly specify the function signature in your chosen programming language.
• Clearly specify how errors are represented or returned when a key is missing from dict.
• The solution should aim for linear time complexity with respect to the length of s, in addition to the cost of dictionary lookups.