LeetCode 1807 - Evaluate the Bracket Pairs of a String

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String

Solution

Problem Understanding

The problem asks us to process a string s that contains bracketed keys like (name) or (age) and replace them with corresponding values provided in the knowledge array. Each element of knowledge is a two-element array [key, value] mapping a key to its replacement value. If a key in s is not present in knowledge, it must be replaced with "?".

We are guaranteed that the brackets are well-formed (every '(' has a corresponding ')'), there are no nested brackets, and each key in knowledge is unique. The length of s can be up to 10^5, and knowledge can have up to 10^5 entries. This suggests that any solution requiring repeated scanning of s or knowledge for each replacement would be too slow. The problem emphasizes efficiency and correctness for potentially large inputs.

Key observations are that keys are always non-empty and that only characters inside brackets are replaced. Characters outside brackets remain unchanged. Edge cases include keys that do not exist in knowledge, multiple occurrences of the same key, and consecutive bracket pairs.

Approaches

The brute-force approach would iterate over the string and, whenever it encounters a bracketed key, scan the knowledge array linearly to find the matching value. While this works correctly, it is inefficient because scanning knowledge each time could result in O(n * m) time complexity, where n is the length of s and m is the number of keys in knowledge. For the largest inputs, this approach could take up to 10^10 operations, which is infeasible.

The optimal approach leverages a hash map to store knowledge for constant-time lookup. As we iterate through s, we build keys character by character when inside brackets. Upon encountering a closing bracket, we replace the bracketed key with its value from the hash map or "?" if the key does not exist. This ensures a single pass over s with O(1) lookups for each key.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(1)	Scan the string and linear search in `knowledge` for each key
Optimal	O(n + m)	O(m)	Single pass with hash map lookup for keys

Algorithm Walkthrough

Convert the knowledge 2D array into a dictionary/hash map key_to_value mapping each key to its value. This allows constant-time lookup for replacements.
Initialize an empty list result to build the output string efficiently and an empty string current_key to accumulate characters of a key while iterating.
Iterate over each character c in the string s.

a. If c is '(', begin accumulating characters into current_key.

b. If c is ')', it signals the end of a key. Retrieve its value from key_to_value or "?" if it is missing, append it to result, and reset current_key.

c. If c is a normal character and we are not inside brackets, append it directly to result. 4. After the iteration, join the result list into a single string and return it.

Why it works: The algorithm maintains the invariant that result contains the fully evaluated string up to the current character. By using a hash map for key lookups, each key is replaced correctly and efficiently. The use of a single pass ensures optimal performance without missing any characters or keys.

Python Solution

from typing import List

class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        key_to_value = {k: v for k, v in knowledge}
        result = []
        current_key = []
        inside_bracket = False
        
        for c in s:
            if c == '(':
                inside_bracket = True
                current_key = []
            elif c == ')':
                inside_bracket = False
                key_str = ''.join(current_key)
                result.append(key_to_value.get(key_str, '?'))
            elif inside_bracket:
                current_key.append(c)
            else:
                result.append(c)
                
        return ''.join(result)

In this implementation, we first convert knowledge into a hash map for O(1) lookups. We iterate through s once. When inside a bracket, characters are accumulated to current_key. Upon encountering ')', we look up the key in the hash map and append the value (or "?") to result. Characters outside brackets are appended directly. Using a list for result is efficient because string concatenation repeatedly in Python is O(n^2) in the worst case.

Go Solution

func evaluate(s string, knowledge [][]string) string {
    keyToValue := make(map[string]string, len(knowledge))
    for _, kv := range knowledge {
        keyToValue[kv[0]] = kv[1]
    }

    var result []byte
    var currentKey []byte
    insideBracket := false

    for i := 0; i < len(s); i++ {
        c := s[i]
        if c == '(' {
            insideBracket = true
            currentKey = currentKey[:0]
        } else if c == ')' {
            insideBracket = false
            keyStr := string(currentKey)
            if val, ok := keyToValue[keyStr]; ok {
                result = append(result, val...)
            } else {
                result = append(result, '?')
            }
        } else if insideBracket {
            currentKey = append(currentKey, c)
        } else {
            result = append(result, c)
        }
    }

    return string(result)
}

In Go, we use []byte for efficient string building. The logic mirrors the Python solution. currentKey accumulates characters inside brackets, and result builds the output. The hash map keyToValue provides constant-time lookups. Edge cases, such as missing keys, are handled with the "?" replacement.

Worked Examples

Example 1: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]

Step	current_key	result	inside_bracket
'('	''	[]	True
'n','a','m','e'	'name'	[]	True
')'	'name'	['bob']	False
'i','s'	''	['bob','i','s']	False
'('	''	['bob','i','s']	True
'a','g','e'	'age'	['bob','i','s']	True
')'	'age'	['bob','i','s','two']	False
'y','e','a','r','s','o','l','d'	''	['bob','i','s','two','y','e','a','r','s','o','l','d']	False

Result: "bobistwoyearsold"

Example 2: s = "hi(name)", knowledge = [["a","b"]]

Result: "hi?"

Example 3: s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]

Result: "yesyesyesaaa"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	n = length of s, m = number of knowledge entries; single pass and O(1) hash lookups
Space	O(m + n)	O(m) for hash map, O(n) for result string

We traverse s once, and each key lookup in the hash map is O(1). Space is dominated by the hash map and the output string.

Test Cases

# Provided examples
assert Solution().evaluate("(name)is(age)yearsold", [["name","bob"],["age","two"]]) == "bobistwoyearsold"
assert Solution().evaluate("hi(name)", [["a","b"]]) == "hi?"
assert Solution().evaluate("(a)(a)(a)aaa", [["a","yes"]]) == "yesyesyesaaa"

# Edge cases
assert Solution().evaluate("()", [["","x"]]) == "?"  # empty key (though problem states non-empty, defensive test)
assert Solution().evaluate("abc", []) == "abc"       # no brackets
assert Solution().evaluate("(x)(y)(z)", [["x","1"],["y","2"]]) == "12?"  # missing key 'z'
assert Solution().evaluate("(longkey)", [["longkey","value"]]) == "value"  # long single key
assert Solution().evaluate("(k)"*1000, [["k","v"]]) == "v"*1000  # stress test multiple same keys

Test	Why
Provided examples	Validate basic functionality
Empty key bracket	Test handling of edge brackets (defensive)
No brackets	Ensure plain strings remain unchanged
Missing key	Test replacement with "?"
Single long key	Verify single key replacement works
Multiple repeated keys	Stress test large repeated replacements

Edge Cases

One important edge case is when `