Problem Description

You are given a replacements mapping and a text string that may contain placeholders formatted as %var%, where each var corresponds to a key in the replacements mapping. Each replacement value may itself contain one or more such placeholders. Each placeholder is replaced by the value associated with its corresponding replacement key.

Your task is to return the fully substituted text string which does not contain any placeholders.

The key challenge here is that replacement values can themselves contain placeholders that need to be resolved. This means you need to recursively substitute placeholders until no more remain.

For example:

• If replacements = [["name", "bob"], ["greeting", "hello %name%"]] and text = "%greeting%!", you would:
  1. Replace %greeting% with "hello %name%"
  2. Then replace %name% with "bob"
  3. Return "hello bob!"

The solution uses a hash table to store the replacement mappings and a recursive function to handle the nested placeholder substitutions. The function finds placeholders marked by % symbols, extracts the key between them, recursively resolves the replacement value, and continues processing the rest of the string.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: While this problem doesn't explicitly mention a graph with nodes and edges, we can model it as a graph problem. Each placeholder and its replacement form a directed edge in a dependency graph. For example, if %greeting% maps to "hello %name%", there's a directed edge from greeting to name.

Is it a tree?

• No: The dependency graph is not necessarily a tree. It could have multiple paths and potentially cycles (though valid inputs shouldn't have cycles as they would lead to infinite substitution).

Is the problem related to directed acyclic graphs?

• No: While the dependency graph is directed, the main focus isn't on DAG properties like topological ordering.

Is the problem related to shortest paths?

• No: We're not finding shortest paths; we need to fully expand all placeholders.

Does the problem involve connectivity?

• No: We're not checking if nodes are connected or finding connected components.

Does the problem have small constraints?

• Yes: The problem typically has manageable constraints since we're dealing with text substitution, and the recursive depth is limited by the number of nested placeholders.

DFS/backtracking?

• Yes: DFS is the perfect fit here. We need to recursively explore each placeholder, resolve its value (which may contain more placeholders), and continue this process until no placeholders remain.

Conclusion: The flowchart suggests using a DFS (Depth-First Search) approach. Each time we encounter a placeholder, we recursively resolve its replacement value before continuing with the rest of the string. This naturally handles nested placeholders through the recursive call stack.

Intuition

The key insight is recognizing that placeholder substitution is inherently a recursive problem. When we replace a placeholder like %greeting% with "hello %name%", we've created a new problem - we now need to resolve %name%. This naturally suggests a depth-first approach where we dive deep into each replacement before moving on.

Think of it like unpacking nested boxes. When you open a box and find another box inside, you need to open that inner box first before you can fully unpack everything. Similarly, when we find a placeholder, we need to fully resolve its replacement value (which might contain more placeholders) before we can consider that part of the text complete.

The recursive nature becomes clear when we consider the substitution process:

1. We scan the text for a placeholder %var%
2. We look up var in our replacements mapping
3. The replacement itself might contain placeholders, so we need to apply the same process to it
4. Only after the replacement is fully resolved can we substitute it back into the original text
5. We continue this process for the rest of the text

This is exactly what DFS does - it explores one path completely before backtracking. In our case, we explore one placeholder's replacement chain completely before moving to the next placeholder in the text.

The beauty of using recursion here is that it naturally handles arbitrary nesting depths. Whether a placeholder resolves directly to plain text or goes through multiple levels of substitution, the same recursive logic applies. The recursion naturally terminates when we encounter text with no placeholders, giving us our base case.

Learn more about Depth-First Search, Breadth-First Search, Graph and Topological Sort patterns.

Solution Approach

The implementation uses a hash table combined with recursion to efficiently handle the placeholder substitutions.

Step 1: Build the Hash Table We first convert the replacements list into a dictionary d where each key-value pair represents a placeholder variable and its replacement text:

d = {s: t for s, t in replacements}

This gives us O(1) lookup time for each placeholder variable.

Step 2: Define the Recursive DFS Function The core logic is in the dfs function that processes a string s:

1. Find the first placeholder's start: Use s.find("%") to locate the first % symbol. If no % is found (returns -1), the string has no placeholders, so we return it as-is.

2. Find the placeholder's end: From position i + 1, find the next % symbol using s.find("%", i + 1). If we can't find a closing %, the string is malformed or incomplete, so we return it as-is.

3. Extract the placeholder key: The variable name is between the two % symbols:

   key = s[i + 1 : j]

4. Recursively resolve the replacement: Look up d[key] and recursively call dfs on it to resolve any nested placeholders:

   replacement = dfs(d[key])

5. Reconstruct the string: Build the result by concatenating:

   • The text before the placeholder: s[:i]
   • The fully resolved replacement: replacement
   • The recursively processed remainder: dfs(s[j + 1:])

Step 3: Process the Input Text Call dfs(text) to start the recursive substitution process on the input text.

The algorithm elegantly handles nested placeholders because when we call dfs(d[key]), it will fully resolve all placeholders in that replacement value before returning. This ensures that by the time we substitute a replacement into our text, it's already fully expanded.

The time complexity depends on the depth and structure of nested placeholders, but each character in the final expanded text is processed once, making it efficient for typical use cases.

Example Walkthrough

Let's walk through a concrete example to see how the recursive DFS approach works.

Given:

• replacements = [["name", "Alice"], ["day", "Monday"], ["greeting", "Hi %name%, happy %day%!"]]
• text = "Message: %greeting%"

Step 1: Build Hash Table

d = {"name": "Alice", "day": "Monday", "greeting": "Hi %name%, happy %day%!"}

Step 2: Process text = "Message: %greeting%"

Call dfs("Message: %greeting%"):

• Find first % at position 9
• Find closing % at position 18
• Extract key: "greeting" (characters between positions 10-17)
• Look up d["greeting"] = "Hi %name%, happy %day%!"
• Recursively call dfs("Hi %name%, happy %day%!")

Step 3: Process nested replacement "Hi %name%, happy %day%!"

In dfs("Hi %name%, happy %day%!"):

• Find first % at position 3
• Find closing % at position 8
• Extract key: "name"
• Look up d["name"] = "Alice"
• Recursively call dfs("Alice") → returns "Alice" (no placeholders)
• Reconstruct: "Hi " + "Alice" + dfs(", happy %day%!")

Step 4: Continue with remaining text ", happy %day%!"

In dfs(", happy %day%!"):

• Find first % at position 8
• Find closing % at position 12
• Extract key: "day"
• Look up d["day"] = "Monday"
• Recursively call dfs("Monday") → returns "Monday" (no placeholders)
• Reconstruct: ", happy " + "Monday" + dfs("!")
• dfs("!") returns "!" (no placeholders)
• Result: ", happy Monday!"

Step 5: Build final result

Working backwards through our recursive calls:

• dfs(", happy %day%!") returns ", happy Monday!"
• dfs("Hi %name%, happy %day%!") returns "Hi Alice, happy Monday!"
• dfs("Message: %greeting%") returns "Message: " + "Hi Alice, happy Monday!" + ""

Final Output: "Message: Hi Alice, happy Monday!"

The key insight is how recursion naturally handles the nested placeholders - we fully resolve each replacement value before substituting it back, ensuring no placeholders remain in the final text.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n × L)

The time complexity consists of two main components:

• Building the dictionary from replacements takes O(m) time, where m is the total length of all replacement mappings
• The DFS traversal processes the text, where:
  • Finding each placeholder pair (two find() operations) takes O(n) time in worst case, where n is the length of the text
  • For each placeholder found, we recursively process the replacement value, which on average has length L
  • The string slicing and concatenation operations also contribute to the complexity
  • In the worst case, we might need to process multiple nested placeholders, leading to O(n × L) time complexity for the DFS portion

Space Complexity: O(m + n × L)

The space complexity includes:

• O(m) space for storing the dictionary d containing all replacement mappings
• The recursion stack depth can go up to O(L) in case of nested placeholder substitutions
• String slicing creates new strings, and in worst case with nested replacements, the total space used for intermediate strings can be O(n × L)
• The combination of dictionary storage and recursive call stack with string operations results in O(m + n × L) space complexity

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Infinite Recursion from Circular Dependencies

The most critical pitfall in this solution is the lack of protection against circular references in the replacements. If replacement values reference each other in a cycle, the recursive function will run indefinitely until hitting the recursion limit.

Example of the problem:

replacements = [["A", "%B%"], ["B", "%A%"]]
text = "%A%"
# This would cause infinite recursion: A -> B -> A -> B -> ...

Solution: Add a visited set to track which variables are currently being resolved:

def recursive_replace(string: str, visiting: set = None) -> str:
    if visiting is None:
        visiting = set()
  
    start_index = string.find("%")
    if start_index == -1:
        return string
  
    end_index = string.find("%", start_index + 1)
    if end_index == -1:
        return string
  
    variable_name = string[start_index + 1 : end_index]
  
    # Check for circular dependency
    if variable_name in visiting:
        # Return the placeholder as-is or raise an error
        return string  # or raise ValueError(f"Circular dependency detected: {variable_name}")
  
    # Add to visiting set before recursive call
    visiting.add(variable_name)
    replacement_value = recursive_replace(replacement_dict[variable_name], visiting)
    visiting.remove(variable_name)  # Remove after processing
  
    return (string[:start_index] + 
           replacement_value + 
           recursive_replace(string[end_index + 1:], visiting))

2. KeyError for Undefined Variables

The current implementation assumes all placeholders have corresponding entries in the replacement dictionary. If a placeholder like %undefined% appears but isn't in the replacements, the code will crash with a KeyError.

Solution: Check if the variable exists before attempting to access it:

variable_name = string[start_index + 1 : end_index]

# Check if variable exists in the dictionary
if variable_name not in replacement_dict:
    # Option 1: Leave the placeholder as-is
    return (string[:start_index] + 
           string[start_index:end_index + 1] + 
           recursive_replace(string[end_index + 1:]))
  
    # Option 2: Replace with empty string
    # return string[:start_index] + recursive_replace(string[end_index + 1:])
  
    # Option 3: Replace with a default value
    # return string[:start_index] + "[UNDEFINED]" + recursive_replace(string[end_index + 1:])

3. Performance Issues with Repeated String Concatenation

While not immediately apparent for small inputs, the repeated string concatenation and substring operations can become inefficient for very large texts or deeply nested replacements. Each concatenation creates a new string object.

Solution: For better performance with large texts, consider using a StringBuilder-like approach or processing positions:

def recursive_replace_optimized(string: str) -> str:
    result = []
    i = 0
  
    while i < len(string):
        if string[i] == '%':
            # Find closing %
            j = string.find('%', i + 1)
            if j == -1:
                result.append(string[i:])
                break
          
            variable_name = string[i + 1:j]
            if variable_name in replacement_dict:
                # Process replacement recursively
                replacement = recursive_replace_optimized(replacement_dict[variable_name])
                result.append(replacement)
                i = j + 1
            else:
                result.append(string[i:j + 1])
                i = j + 1
        else:
            # Find next % or end of string
            next_percent = string.find('%', i)
            if next_percent == -1:
                result.append(string[i:])
                break
            else:
                result.append(string[i:next_percent])
                i = next_percent
  
    return ''.join(result)