Evaluate the Bracket Pairs of a String - Practice Coding Problems

Evaluate the Bracket Pairs of a String - 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] = [key_i, value_i] indicates that key key_i has a value of value_i.

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

Replace key_i and the bracket pair with the key's corresponding value_i.
If you do not know the value of the key, you will replace key_i and the bracket pair with a question mark "?".

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.

Input & Output

Example 1 — Basic Replacement

$ Input: s = "(name)is(age)yearsold", knowledge = [["name","Bob"],["age","20"]]

› Output: "Bobis20yearsold"

💡 Note: The key "name" is replaced with "Bob" and "age" is replaced with "20", resulting in "Bobis20yearsold"

Example 2 — Unknown Key

$ Input: s = "hi(name)", knowledge = [["age","25"]]

› Output: "hi?"

💡 Note: The key "name" is not found in knowledge, so it's replaced with "?"

Example 3 — No Brackets

$ Input: s = "hello", knowledge = [["name","Bob"]]

› Output: "hello"

💡 Note: No bracket pairs found, so the string remains unchanged

Constraints

1 ≤ s.length ≤ 10⁵
0 ≤ knowledge.length ≤ 10⁵
knowledge[i].length == 2

Visualization

Tap to expand

Understanding the Visualization

Input

String with bracket pairs and knowledge array

Process

Find bracket pairs and lookup values

Output

String with replacements or '?' for unknown keys

Key Takeaway

🎯 Key Insight: Use hash map to transform O(n×k) linear searches into O(n+k) with constant-time lookups

Asked in

f Facebook 15 a Amazon 12 M Microsoft 8

The key insight is to use a hash map to convert O(k) linear searches into O(1) lookups. Build the hash map once from the knowledge array, then scan the string to find bracket pairs and replace them instantly. Best approach is hash map optimization with Time: O(n+k), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Optimization	O(n+k)	O(k)	Build hash map first, then scan string once with O(1) lookups
Brute Force Linear Search	O(n×k)	O(1)	For each bracket pair, search through all knowledge entries linearly

Hash Map Optimization — Algorithm Steps

Step 1: Build hash map from knowledge array
Step 2: Scan string to find bracket pairs
Step 3: Extract key and lookup in hash map in O(1)
Step 4: Replace with value or '?' if not found

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Hash Map

Create map from knowledge array

Scan & Lookup

Extract keys and lookup in O(1)

Replace

Substitute instantly with values

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* s, char knowledge[][2][100], int knowledgeSize) {
    int len = strlen(s);
    char* result = (char*)malloc(1000 * sizeof(char));
    int resultIndex = 0;
    int i = 0;
    
    while (i < len) {
        if (s[i] == '(') {
            // Find the closing bracket
            int j = i + 1;
            while (j < len && s[j] != ')') {
                j++;
            }
            
            // Extract the key
            char key[100];
            int keyLen = j - i - 1;
            strncpy(key, s + i + 1, keyLen);
            key[keyLen] = '\0';
            
            // Search for the key in knowledge (C doesn't have built-in hash map)
            int found = 0;
            for (int k = 0; k < knowledgeSize; k++) {
                if (strcmp(knowledge[k][0], key) == 0) {
                    strcpy(result + resultIndex, knowledge[k][1]);
                    resultIndex += strlen(knowledge[k][1]);
                    found = 1;
                    break;
                }
            }
            
            if (!found) {
                result[resultIndex++] = '?';
            }
            
            i = j + 1;
        } else {
            result[resultIndex++] = s[i];
            i++;
        }
    }
    
    result[resultIndex] = '\0';
    return result;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    // Simple parsing for demo - in practice would need proper JSON parsing
    char knowledge[10][2][100];
    int knowledgeSize = 0;
    
    char* result = solution(s, knowledge, knowledgeSize);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n+k)

O(k) to build hash map + O(n) to scan string once

✓ Linear Growth

Space Complexity

O(k)

Hash map stores k knowledge pairs

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler