Skip to main content
Talentd

Evaluate the Bracket Pairs of a String - Solution & Explanation

MediumArrayHash TableString13 min readAsked at: Google, Remitly
Practice this problem

Problem Statement

You are given a string s that contains some bracket pairs, with each pair containing a non-empty key.

  • For example, in the string "(name)is(age)yearsold", there are two bracket pairs that contain the keys "name" and "age".

You know the values of a wide range of keys. This is represented by a 2D string array knowledge where each knowledge[i] = [keyi, valuei] indicates that key keyi has a value of valuei.

You are tasked to evaluate all of the bracket pairs. When you evaluate a bracket pair that contains some key keyi, you will:

  • Replace keyi and the bracket pair with the key's corresponding valuei.
  • If you do not know the value of the key, you will replace keyi and the bracket pair with a question mark "?" (without the quotation marks).

Each key will appear at most once in your knowledge. There will not be any nested brackets in s.

Return the resulting string after evaluating all of the bracket pairs.

 

Example 1:

Input: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
Output: "bobistwoyearsold"
Explanation:
The key "name" has a value of "bob", so replace "(name)" with "bob".
The key "age" has a value of "two", so replace "(age)" with "two".

Example 2:

Input: s = "hi(name)", knowledge = [["a","b"]]
Output: "hi?"
Explanation: As you do not know the value of the key "name", replace "(name)" with "?".

Example 3:

Input: s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]
Output: "yesyesyesaaa"
Explanation: The same key can appear multiple times.
The key "a" has a value of "yes", so replace all occurrences of "(a)" with "yes".
Notice that the "a"s not in a bracket pair are not evaluated.

 

Constraints:

  • 1 <= s.length <= 105
  • 0 <= knowledge.length <= 105
  • knowledge[i].length == 2
  • 1 <= keyi.length, valuei.length <= 10
  • s consists of lowercase English letters and round brackets '(' and ')'.
  • Every open bracket '(' in s will have a corresponding close bracket ')'.
  • The key in each bracket pair of s will be non-empty.
  • There will not be any nested bracket pairs in s.
  • keyi and valuei consist of lowercase English letters.
  • Each keyi in knowledge is unique.

Approach Overview

Problem Overview: You receive a string s containing keys wrapped in parentheses such as (name) and a knowledge base of key–value pairs. Every key inside brackets must be replaced with its mapped value. If a key does not exist in the knowledge base, replace it with "?". The challenge is scanning the string efficiently while resolving keys quickly.

Approach 1: Using Dictionary or Map for Fast Key Lookup (O(n) time, O(k) space)

Store all knowledge pairs in a hash map so each key lookup runs in constant time. Iterate through the string character by character. When you encounter '(', start collecting characters until the closing ')' to form the key. Perform a direct hash lookup in the map and append the mapped value (or "?" if the key does not exist) to the result string. Characters outside brackets are appended normally. This approach processes each character once, making the total runtime O(n) where n is the length of the string, while the map requires O(k) space for k knowledge entries. The method relies heavily on hash table lookups and efficient string traversal.

Approach 2: Using Regular Expressions and String Replacement (O(n + m) time, O(k) space)

Another option uses a regular expression to locate patterns like \((.*?)\). First store the knowledge pairs in a map for constant-time lookup. The regex engine scans the string to find every bracketed key. For each match, replace the captured key with its corresponding value from the map or "?" if missing. This approach is concise and works well in languages with strong regex support such as Java or C#. Runtime is roughly O(n + m), where n is the string length and m is the number of matches processed. Space usage remains O(k) for storing the mapping. While elegant, regex may introduce overhead compared with manual parsing.

Recommended for interviews: The dictionary + manual scan approach is what interviewers expect. It demonstrates strong control over string parsing and efficient use of a hash table. Regex solutions are shorter but hide the underlying logic and may not always be optimal in performance-critical situations. Showing the direct parsing approach proves you can manage edge cases, handle missing keys, and maintain linear time complexity.

Approach 1: Approach 1: Using Dictionary or Map for Fast Key Lookup

This approach leverages a hashmap (or dictionary) to store the 'knowledge' key-value pairs for efficient lookup. The idea is to traverse the input string 's' character by character, recognizing and processing the sections enclosed in brackets, and replacing them with their corresponding values from the hashmap. If the key isn't found in the hashmap, replace it with a '?'.

The code first creates a dictionary from the 'knowledge' list for quick key look-ups. It then iterates over the string 's', identifying bracketed keys and replacing them based on the dictionary. If a key is not found, it substitutes it with '?'. The result list gathers the output string which is constructed using efficient concatenation.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n + k) where n is the length of s and k is the length of the knowledge list. Space Complexity: O(k) for storing the dictionary.

Try this approach in the editor →

Approach 2: Approach 2: Using Regular Expressions and String Replacement

This approach takes advantage of regular expressions to identify bracketed pairs and performed batch string replacements based on the knowledge. This is efficient for scenarios with multiple replacements.

In this solution, a HashMap is utilized to map knowledge keys to their values. The string is traversed, and when bracketed sections are encountered, they are processed and replaced in the output using the hashmap for swift retrieval, much like the first approach but detailed for Java syntax.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n + k) where n is the length of s and k is the length of the knowledge list. Space Complexity: O(k) due to storage of dictionary elements.

Try this approach in the editor →

Approach 3: Hash Table + Simulation

First, we use a hash table d to record the key-value pairs in knowledge.

Then we traverse the string s. If the current character is an open parenthesis '(', we start traversing from the current position until we encounter a close parenthesis ')'. At this point, the string within the parentheses is the key. We look for the corresponding value of this key in the hash table d. If found, we replace the value within the parentheses with it, otherwise, we replace it with '?'.

The time complexity is O(n + m), and the space complexity is O(L). Here, n and m are the lengths of the string s and the list knowledge respectively, and L is the sum of the lengths of all strings in knowledge.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Dictionary or Map for Fast Key Lookup

Time Complexity: O(n + k) where n is the length of s and k is the length of the knowledge list. Space Complexity: O(k) for storing the dictionary.

Approach 2: Using Regular Expressions and String Replacement

Time Complexity: O(n + k) where n is the length of s and k is the length of the knowledge list. Space Complexity: O(k) due to storage of dictionary elements.

Hash Table + Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dictionary / Map with Manual String ParsingO(n)O(k)Best general solution. Linear scan with constant-time key lookup.
Regular Expression ReplacementO(n + m)O(k)Useful when regex libraries are strong and concise code is preferred.

Video Solution

LeetCode 1807. Evaluate the Bracket Pairs of a String | Visualization | Python • AH Tech • 409 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Evaluate the Bracket Pairs of a String easy or hard?
Evaluate the Bracket Pairs of a String is rated Medium difficulty. The logic is straightforward once you recognize the need for a hash map and controlled string parsing, but handling bracket detection and missing keys correctly requires careful implementation.
Evaluate the Bracket Pairs of a String Python/Java solution
Python and JavaScript solutions typically use a dictionary or object map and iterate through the string character by character. Java and C# implementations may also use regex-based replacement combined with a map lookup. Both implementations aim for O(n) traversal with O(k) extra space.
How to solve Evaluate the Bracket Pairs of a String in O(n)?
Create a hash map from the knowledge list so every key can be retrieved in O(1). Iterate through the string and detect segments inside parentheses. Build the key string until the closing bracket, then append the mapped value or '?' if the key does not exist. Since every character is visited once, the algorithm runs in linear time.
What is the best approach for Evaluate the Bracket Pairs of a String?
The most efficient approach uses a hash map to store key-value pairs from the knowledge base and then scans the string once. When encountering a bracketed key, extract it and perform a constant-time lookup in the map. This results in O(n) time complexity and O(k) space complexity where k is the number of knowledge pairs.
Is Evaluate the Bracket Pairs of a String asked at Google/Amazon/Meta?
Problems involving string parsing with hash maps are common in interviews at companies like Amazon, Google, and Meta. While this exact problem may appear on platforms like LeetCode, the underlying pattern—parsing structured strings and resolving keys via hash tables—is frequently tested.
What data structure is used in Evaluate the Bracket Pairs of a String?
A hash table (dictionary or map) is the primary data structure. It stores key-value pairs from the knowledge base so each bracketed key can be resolved in constant time. The solution also relies on sequential string traversal to detect parentheses and build keys.
What is the time complexity of Evaluate the Bracket Pairs of a String?
The optimal solution runs in O(n) time, where n is the length of the input string. Each character is processed once while keys inside parentheses are extracted and resolved using constant-time hash map lookups. Space complexity is O(k) for storing the knowledge mapping.

Ready to solve this problem?

Practice Evaluate the Bracket Pairs of a String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Apply Substitutions