Introduction

LeetCode 1807, Evaluate the Bracket Pairs of a String, is a string-processing problem that combines two common techniques:

1. Using a HashMap for fast key-value lookup
2. Traversing a string while keeping track of whether the current characters belong to a bracket pair

The string contains ordinary characters as well as bracketed keys such as:

A separate knowledge list provides the value associated with each known key.

For every bracket pair:

1. If the key exists in knowledge, replace the entire pair with its value.
2. If the key is not present, replace the entire pair with ?.

For example:

with:

becomes:

The main challenge is identifying exactly which characters belong to a bracketed key while keeping the characters outside brackets unchanged.

Question Link

LeetCode 1807 – Evaluate the Bracket Pairs of a String

Understanding the Problem

Consider:

The bracket pairs are:

The text outside the brackets is:

Suppose:

Then the transformation is:

So the final result becomes:

The characters outside brackets should not be interpreted as keys.

For example:

with:

produces:

The final aaa remains unchanged because those characters are not inside brackets.

Approach

The solution can be divided into two parts.

Store the Knowledge in a HashMap

The knowledge array contains pairs such as:

These pairs are stored in a HashMap:

This gives direct access to a value using its key.

For example:

returns:

And:

can be used to determine whether a key exists.

Because each key appears at most once in knowledge, there is no need to handle duplicate key definitions.

Detecting a Bracketed Key

The solution uses a boolean variable:

This represents whether the current position is inside a bracket pair.

When the character immediately before the current character is '(':

the solution starts collecting a new key.

For example:

Once n is reached, the previous character is '(', so the solution begins collecting:

When ')' is encountered:

the key is complete.

The solution can then look it up in the map.

Replacing the Key

When the closing bracket is found, the code checks whether the collected key exists:

If the key is known:

If the key is unknown:

This directly follows the problem statement.

Keeping Characters Outside Brackets

Characters that are not part of a bracketed key are added directly to the result:

This is important because ordinary characters must remain unchanged.

For:

the characters:

are outside the brackets and are therefore copied directly.

The key:

is evaluated separately.

Java Solution

Here is the submitted solution with comments explaining the important parts:

Dry Run

Consider:

and:

Initially:

Reading (name)

The scanner encounters '('.

The next characters are collected as the key:

When ')' is reached:

The map contains "name":

So:

Reading is

These characters are outside brackets:

They are copied directly:

Reading (age)

The key is collected:

At the closing bracket:

The map contains:

So:

The final result is:

Handling an Unknown Key

Consider:

with:

The map contains only:

When the scanner reaches:

the collected key is:

But:

is false.

Therefore the entire bracket pair is replaced with:

The result becomes:

This is an important part of the problem because unknown keys should not remain in the output.

Why a HashMap Works Well

The knowledge list can contain up to 10^5 entries.

Searching through the entire list for every bracket pair would be unnecessarily expensive.

Instead, the solution converts it into:

using a HashMap.

Then a lookup is expected O(1).

This makes the solution efficient even when the knowledge list is large.

A Small Implementation Improvement

The submitted solution uses:

and repeatedly performs:

Java String objects are immutable, so repeatedly concatenating strings can create many intermediate objects.

A StringBuilder is more appropriate when constructing a result character by character.

The same approach can therefore be written as:

This version expresses the parsing states more directly:

Complexity Analysis

Let:

1. n = length of s
2. k = number of entries in knowledge

Building the HashMap requires:

Time: O(k)

The string is scanned once:

Time: O(n)

Therefore, the overall expected complexity is:

Time Complexity: O(n + k)

The HashMap stores all known keys and values.

Space Complexity: O(k + n)

The O(n) component accounts for the output and temporary string-building structures.

Interview Tip

This problem is a good example of a state-based string traversal.

Instead of trying to manipulate the entire string repeatedly, scan it once and maintain a small amount of state:

When a string contains delimiters such as:

a similar state-based approach can often simplify the implementation.

The second important pattern is recognizing when a HashMap is appropriate: whenever many lookups need to be performed using a unique key.

Conclusion

LeetCode 1807 is primarily a string parsing + HashMap lookup problem.

The solution first converts the knowledge list into a key-value map. It then scans the string and distinguishes between characters inside and outside brackets.

For every bracketed key:

The important implementation ideas are:

1. Use a HashMap for fast key lookup.
2. Track whether the scanner is inside a bracket pair.
3. Collect characters between '(' and ')'.
4. Preserve characters outside brackets.
5. Return the first available result after processing the complete string.

The submitted approach follows this logic correctly. For production-quality Java code, StringBuilder is preferable to repeated String concatenation when constructing the result.