Evaluate the Bracket Pairs of a String

Given a string containing non-nested bracketed keys and a list of key→value pairs, replace each "(key)" with its corresponding value or "?" if the key is unknown. The core challenge is to build a lookup map and perform an efficient single-pass parse (linear time) to reconstruct the resulting string for inputs up to 10^5 characters.