Scale Engineer

Evaluate the Bracket Pairs of a String

Med
#1653Time: 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.1 company
Data structures
ArrayHash TableString
Companies
Remitly

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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().

Walkthrough

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.

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();    }}

Complexity

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.

Trade-offs

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.

Solutions

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();  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem