Evaluate the Bracket Pairs of a String: Hash Map Substitution

You are given a string s that contains bracket pairs with keys inside them, and a 2D array knowledge where each entry is [key, value]. For every bracket pair (key) in the string, replace it with the corresponding value from knowledge, or with "?" if the key is not found. Return the resulting string.

This is LeetCode 1807: Evaluate the Bracket Pairs of a String.

Why this problem matters

Template substitution is everywhere: configuration files, email templates, URL routing, string interpolation in programming languages. This problem distills that pattern into its simplest form. You scan for delimited placeholders, look up replacements, and build a result. If you have ever used Python f-strings or Mustache templates, you already understand the concept. The challenge is translating that intuition into clean, efficient code that handles missing keys gracefully.

Beyond interviews, this exact scan-lookup-replace pipeline shows up in real codebases constantly. Practicing it here means you will recognize the pattern instantly the next time you see it, whether in a coding round or at work.

The key insight

Convert knowledge to a hash map for O(1) lookups. Then scan the string character by character: when you see (, collect characters until ) to get the key, look it up in the map, and append the value (or "?" if the key is missing). When you are outside brackets, just append the character directly to the result.

Use a list to collect the result parts and join them at the end. This avoids the quadratic cost of repeated string concatenation, which matters when the input string is large.

The solution

def evaluate(s: str, knowledge: list[list[str]]) -> str:
    lookup = {k: v for k, v in knowledge}
    result = []
    i = 0

    while i < len(s):
        if s[i] == '(':
            j = i + 1
            while s[j] != ')':
                j += 1
            key = s[i + 1:j]
            result.append(lookup.get(key, '?'))
            i = j + 1
        else:
            result.append(s[i])
            i += 1

    return ''.join(result)

First, we build the lookup dictionary from the knowledge pairs. This takes one pass over the knowledge array and gives us O(1) access to any value by key.

Then we scan the string with pointer i. When s[i] is (, we set up a second pointer j at i + 1 and walk it forward until we find the closing ). The substring between the two pointers is the key. We use lookup.get(key, '?') to fetch the value, falling back to "?" for unknown keys. Then we jump i past the closing parenthesis.

When s[i] is anything other than (, it is literal text. We append it directly and move i forward by one.

At the end, ''.join(result) combines all the collected pieces into the final string.

Visual walkthrough

Here is the full scan of "(name)is(age)yearsold" with the knowledge map {name: bob, age: two}. Each step highlights the current segment being processed and shows the result building up incrementally.

Notice how the algorithm never backtracks. Each character is visited at most once by either pointer i or pointer j. The two pointers together cover the entire string in a single pass.

Complexity analysis

Time: O(n + m) where n is the length of the string and m is the total size of the knowledge entries. Building the map is O(m), scanning the string is O(n).

Space: O(n + m) for the hash map and the result list.

The building blocks

1. Bracket/delimiter extraction

The pattern of scanning for opening and closing delimiters to extract content between them is reusable across many problems. You set one pointer at the opener and walk a second pointer to the closer, then slice the substring between them.

if s[i] == '(':
    j = i + 1
    while s[j] != ')':
        j += 1
    content = s[i + 1:j]
    i = j + 1

This two-pointer extraction works any time you have matched delimiters and no nesting. For nested delimiters, you would need a stack instead.

2. Dictionary with default values

Using dict.get(key, default) for safe lookups with fallbacks is a pattern you will reach for constantly. It avoids KeyError exceptions and keeps your code clean by handling the missing-key case inline.

lookup = {k: v for k, v in pairs}
result = lookup.get(key, '?')

You can also use collections.defaultdict when you need a default for every access, but get with a default is usually cleaner when you only need it in specific places.

Edge cases

• No bracket pairs: the string has no parentheses, so you return it unchanged. Every character is literal text.
• Unknown key: the key is not in the knowledge map. Replace with "?" as specified.
• Empty key: "()" with nothing between the brackets. The key is an empty string. If it is not in the map, it becomes "?".
• Adjacent bracket pairs: "(a)(b)" with no text between them. The algorithm handles this naturally since it jumps past the closing ) and immediately sees the next (.
• All brackets: the entire string is bracket pairs with no literal text. The loop only hits the if branch, never the else.
• Large knowledge map: the hash map ensures lookups stay O(1) regardless of how many entries there are.

From understanding to recall

Template substitution combines three pieces: scanning for delimiters, extracting keys, and looking up replacements. Each piece is simple on its own, but under interview pressure it is easy to fumble the pointer arithmetic or forget to handle missing keys. Did you slice from i + 1 to j, or from i to j + 1? Did you remember to advance i past the closing parenthesis?

Spaced repetition drills each piece until the scan-extract-lookup-append pattern is automatic. You write the two-pointer extraction from scratch, check yourself, and repeat at growing intervals. After a few rounds, the index math flows out without hesitation.

Related posts

• Group Anagrams - Uses hash maps to group strings by canonical keys
• Find the Index of the First Occurrence in a String - String scanning patterns for finding substrings
• Valid Parentheses - Working with bracket matching fundamentals

CodeBricks breaks Evaluate the Bracket Pairs of a String into its delimiter-extraction and hash-map-lookup building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a template substitution problem shows up in your interview, you do not fumble the pointers. You just write it.