Replace tokens in a string using delimiter-based key-value rules

You are given a string s that may contain multiple tokens. Each token has the format: it starts with a semicolon ; and ends with a colon :, and the substring in between is the token key, e.g. ;x: or ;name:. You are also given a map dict from keys to replacement strings (e.g. { "x": "y" } means replace ;x: with y). Replace every substring in s that matches the token format and whose key exists in dict with its mapped value, and output the resulting string. If a substring has the correct token format but its key is not in dict, leave it unchanged. Input Line 1: string s Line 2: integer m, number of mappings Next m lines: key value meaning dict[key] = value Output Print the transformed string. Notes / Constraints The interview explicitly stated that any recognizable token starts with ; and ends with :. Let n = len(s). Aim for an efficient scan-and-replace approach (avoid trying all keys at each ;). Examples s = "hello ;x: world", dict = {"x": "y"} -> "hello y world" s = ";a:;b:", dict = {"a":"1","b":"2"} -> "12" s = "keep ;unknown: token", dict = {"x":"y"} -> "keep ;unknown: token" Example Input hello ;x: world 1 x y Output hello y world