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