1807. Evaluate the Bracket Pairs of a String

Array
Hash Table
String

TIME

O(n + m)

SPACE

O(n + m)

Intuition

Nothing about the replacement depends on context, so this is a single left-to-right pass with a lookup table. Since brackets are never nested, the parser only needs one bit of state: inside a key or not. Building the result as a list of chunks and joining once avoids the quadratic cost of repeated string concatenation.

Approach

Build lookup = {key: value} from knowledge.
Walk s:
- ( → switch to key mode, clear the key buffer
- ) → switch back, append lookup.get(key, "?")
- any other character → append it to the key buffer if in key mode, else straight to the output
Join the chunks.

Complexity

Time: O(n + m) where n = len(s) and m = len(knowledge)
Space: O(n + m) for the lookup table and the output

Edge Cases

Empty knowledge → every bracket pair becomes "?"
The same key used several times, including when unknown (Example 3)
Letters outside brackets that happen to match a key are left alone ("(a)(a)(a)aaa" keeps the trailing aaa)
A string with no brackets at all → returned unchanged
Keys present in knowledge but never used in s → ignored
Building with "".join(parts) rather than += keeps the pass linear

Code

from typing import List


class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        """
        1807. Evaluate the Bracket Pairs of a String
        Time: O(n + m)
        Space: O(n + m)
        """
        lookup = {key: value for key, value in knowledge}

        parts = []
        key_chars = []
        in_key = False

        for ch in s:
            if ch == "(":
                in_key = True
                key_chars.clear()
            elif ch == ")":
                in_key = False
                parts.append(lookup.get("".join(key_chars), "?"))
            elif in_key:
                key_chars.append(ch)
            else:
                parts.append(ch)

        return "".join(parts)

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 1807. Evaluate the Bracket Pairs of a String
 * Time: O(n + m)
 * Space: O(n + m)
 */
class Solution {
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> lookup = new HashMap<>();
        for (List<String> pair : knowledge) {
            lookup.put(pair.get(0), pair.get(1));
        }

        StringBuilder out = new StringBuilder();
        StringBuilder key = new StringBuilder();
        boolean inKey = false;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                inKey = true;
                key.setLength(0);
            } else if (ch == ')') {
                inKey = false;
                out.append(lookup.getOrDefault(key.toString(), "?"));
            } else if (inKey) {
                key.append(ch);
            } else {
                out.append(ch);
            }
        }

        return out.toString();
    }
}