Practice/Google/String Template Substitution with Variable Replacement

String Template Substitution with Variable Replacement

CodingMust

Problem

Build a template expansion engine that processes strings containing placeholders and replaces them with values from a provided dictionary. Placeholders are enclosed in curly braces like {variable}. The challenge is that replacement values themselves may contain additional placeholders, requiring recursive or iterative resolution until no more substitutions can be made.

Your function should continue expanding placeholders until either all placeholders are resolved or no further progress can be made (when placeholders reference missing keys).

Requirements

1. Replace all occurrences of {key} in the template with the corresponding value from the mapping dictionary
2. Handle nested substitutions where replacement values contain additional placeholders
3. Continue expanding until no more substitutions are possible
4. Leave unresolved placeholders (those without mappings) unchanged in the result
5. Prevent infinite loops when circular references exist in the mapping

Constraints

• Template string length: 1 ≤ length ≤ 1000
• Number of mappings: 0 ≤ count ≤ 100
• Placeholder names consist of alphanumeric characters and underscores
• The solution should complete in reasonable time even with multiple nested levels
• Time complexity: O(n × m × k) where n is template length, m is number of mappings, k is nesting depth
• Space complexity: O(n) for the result string

Examples

Example 1:

Input: template = "User {name} has {role} access" mapping = {"name": "John", "role": "admin"} Output: "User John has admin access" Explanation: Direct substitution of two placeholders with their values.

Example 2:

Input: template = "Message: {msg}" mapping = {"msg": "{prefix}: {content}", "prefix": "INFO", "content": "System ready"} Output: "Message: INFO: System ready" Explanation: The value for 'msg' contains two more placeholders that need expansion.

Example 3:

Input: template = "{a} and {b}" mapping = {"a": "{b}", "b": "{a}"} Output: "{a} and {b}" Explanation: Circular reference detected - substitutions cannot progress, so original placeholders remain.