# Evaluate the Bracket Pairs of a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/evaluate-the-bracket-pairs-of-a-string)
Canonical: https://scaleengineer.com/dsa/problems/evaluate-the-bracket-pairs-of-a-string
**Data structures:** Array, Hash Table, String
**Companies:** [Remitly](https://scaleengineer.com/companies/remitly)
---
## Problem
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.

# Approaches
## Brute Force with Linear Scan
This approach involves iterating through the input string `s` and, for each bracket pair encountered, performing a linear search through the `knowledge` list to find the corresponding value. It's simple to understand but inefficient.
**Time:** O(N + B * M * K), where `N` is the length of `s`, `B` is the number of bracket pairs in `s`, `M` is the number of entries in `knowledge`, and `K` is the maximum length of a key. The `N` comes from iterating through the string `s`. For each of the `B` bracket pairs, we perform a linear scan of `M` knowledge entries, with string comparisons taking up to `O(K)` time. In the worst case, `B` can be proportional to `N`, leading to a complexity of `O(N * M * K)`. · **Space:** O(L), where `L` is the length of the output string. The space is primarily used by the `StringBuilder` to construct the result. In the worst case, `L` can be `O(N + B * V)`, where `N` is the length of `s`, `B` is the number of bracket pairs, and `V` is the maximum length of a value.
**Pros:** Simple to conceptualize and implement without requiring any advanced data structures.; Uses minimal extra space, aside from the space needed for the output string.
**Cons:** Extremely inefficient for large inputs due to the nested loop structure (iterating through `s` and for each key, iterating through `knowledge`).; Will likely cause a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.
### Explanation
We use a `StringBuilder` to construct the final string. We iterate through the string `s` character by character. When we are not inside a bracket pair, we simply append the character to our `StringBuilder`. When we encounter an opening bracket `'('`, we note the starting position of the key. Upon finding the matching closing bracket `')'`, we extract the key contained within.

Once a key is extracted, we perform a brute-force search: we iterate through the entire `knowledge` list from beginning to end. For each entry `[key_i, value_i]`, we compare `key_i` with our extracted key. If a match is found, we append the corresponding `value_i` to our `StringBuilder` and stop searching for this key. If we traverse the entire `knowledge` list without finding a match, we append a question mark `'?'` instead. This process is repeated for every bracket pair in the string `s`.

```java
class Solution {
    public String evaluate(String s, java.util.List<java.util.List<String>> knowledge) {
        StringBuilder result = new StringBuilder();
        int keyStart = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                keyStart = i + 1;
            } else if (c == ')') {
                String key = s.substring(keyStart, i);
                String value = "?";
                for (java.util.List<String> pair : knowledge) {
                    if (pair.get(0).equals(key)) {
                        value = pair.get(1);
                        break;
                    }
                }
                result.append(value);
                keyStart = -1;
            } else {
                if (keyStart == -1) {
                    result.append(c);
                }
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Initialize a `StringBuilder` named `result`.
- Initialize an integer `keyStart` to `-1`. This variable will hold the starting index of a key when we are inside a bracket pair.
- Iterate through the input string `s` with an index `i` from `0` to `s.length() - 1`.
- At each character `c = s.charAt(i)`:
  - If `c` is `'('`, it marks the beginning of a key. Set `keyStart = i + 1`.
  - If `c` is `')'`, it marks the end of a key. 
    - Extract the `key` using `s.substring(keyStart, i)`.
    - Initialize a `value` string to `"?"`.
    - Linearly iterate through the `knowledge` list. For each `pair`, if `pair.get(0)` equals the `key`, update `value` to `pair.get(1)` and break the inner loop.
    - Append the final `value` to the `result`.
    - Reset `keyStart` to `-1` to indicate we are now outside a bracket pair.
  - If `c` is any other character and `keyStart` is `-1` (meaning we are not inside a bracket), append `c` to `result`.
- After the loop finishes, return `result.toString()`.

## Optimized Approach using HashMap
This approach significantly improves performance by pre-processing the `knowledge` list into a `HashMap`. A `HashMap` provides average O(1) time complexity for lookups, which eliminates the costly linear search for each key.
**Time:** O(M * K + N + L), where `M` is the number of knowledge pairs, `K` is the max key length, `N` is the length of `s`, and `L` is the length of the output string. 
- `O(M * K)` is required to build the HashMap.
- `O(N)` is for the single pass over the input string `s`.
- The string operations (substring, append) contribute to the overall complexity, which is related to the output length `L`. · **Space:** O(M * (K + V) + L), where `M` is the number of knowledge pairs, `K` and `V` are the maximum lengths of keys and values, and `L` is the length of the output string. This includes `O(M * (K + V))` for the `HashMap` and `O(L)` for the `StringBuilder`.
**Pros:** Highly efficient time complexity, making it suitable for large inputs.; The use of a `HashMap` makes the lookup logic clean and concise.
**Cons:** Requires additional memory to store the `HashMap`. The space complexity is higher than the brute-force approach.
### Explanation
The core idea of this optimized approach is to trade space for time. We first create a `HashMap` to store the key-value pairs from the `knowledge` list. This pre-processing step allows for near-instantaneous retrieval of any key's value.

The algorithm begins by iterating through the `knowledge` list just once to populate the `HashMap`. The keys from `knowledge` become the map's keys, and the values from `knowledge` become the map's values.

After the map is built, we process the string `s` in a single pass. We use a `StringBuilder` to construct the result. When we identify a bracketed key, we extract it. Instead of performing a linear search, we query our `HashMap`. The `getOrDefault` method is particularly useful here: it fetches the value for our key if it exists, and returns a specified default value (`"?"`) if it doesn't. This single operation replaces the entire inner loop of the brute-force method, drastically reducing the overall time complexity.

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

class Solution {
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> knowledgeMap = new HashMap<>();
        for (List<String> pair : knowledge) {
            knowledgeMap.put(pair.get(0), pair.get(1));
        }

        StringBuilder result = new StringBuilder();
        int keyStart = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                keyStart = i + 1;
            } else if (c == ')') {
                String key = s.substring(keyStart, i);
                result.append(knowledgeMap.getOrDefault(key, "?"));
                keyStart = -1;
            } else {
                if (keyStart == -1) {
                    result.append(c);
                }
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Create a `HashMap<String, String>` called `knowledgeMap`.
- Iterate through the `knowledge` list. For each `[key, value]` pair, insert it into `knowledgeMap` using `knowledgeMap.put(key, value)`.
- Initialize a `StringBuilder` named `result` and an integer `keyStart` to `-1`.
- Iterate through the input string `s` with an index `i`.
- At each character `c = s.charAt(i)`:
  - If `c` is `'('`, set `keyStart = i + 1`.
  - If `c` is `')'`, extract the `key` using `s.substring(keyStart, i)`.
    - Look up the key in `knowledgeMap` using `knowledgeMap.getOrDefault(key, "?")`. This will return the corresponding value if the key exists, or `"?"` otherwise.
    - Append the retrieved value to `result`.
    - Reset `keyStart` to `-1`.
  - If `c` is any other character and `keyStart` is `-1`, append `c` to `result`.
- After the loop, return `result.toString()`.

# Solutions
### Java

```java
class Solution {
public
  String evaluate(String s, List<List<String>> knowledge) {
    Map<String, String> d = new HashMap<>(knowledge.size());
    for (var e : knowledge) {
      d.put(e.get(0), e.get(1));
    }
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < s.length(); ++i) {
      if (s.charAt(i) == '(') {
        int j = s.indexOf(')', i + 1);
        ans.append(d.getOrDefault(s.substring(i + 1, j), "?"));
        i = j;
      } else {
        ans.append(s.charAt(i));
      }
    }
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string evaluate(string s, vector<vector<string>> &knowledge) {
    unordered_map<string, string> d;
    for (auto &e : knowledge) {
      d[e[0]] = e[1];
    }
    string ans;
    for (int i = 0; i < s.size(); ++i) {
      if (s[i] == '(') {
        int j = s.find(")", i + 1);
        auto t = s.substr(i + 1, j - i - 1);
        ans += d.count(t) ? d[t] : "?";
        i = j;
      } else {
        ans += s[i];
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str: d = {a: b for a, b in knowledge} i, n = 0, len(s) ans = [] while i < n: if s[i] == '(': j = s . find(')', i + 1) ans . append(d . get(s[i + 1: j], '?')) i = j else: ans . append(s[i]) i += 1 return '' . join(ans)

```