Expand Recursive Key-Value Placeholders in a Template

Problem Statement

You are given a template string template and a dictionary of key-value pairs mapping. Your goal is to resolve and replace all placeholders in template with their corresponding expanded values.

Placeholders follow these rules:

• A placeholder is denoted by %KEY%, where KEY consists of one or more alphanumeric characters or underscores ([A-Za-z0-9_]+).
• Values in mapping may themselves contain placeholders (e.g., %ANOTHER_KEY%), which must be recursively expanded.
• Two consecutive percent characters %% denote an escaped literal % character and should not be parsed as placeholder delimiters.
• If a circular dependency is detected among keys during expansion (e.g., A refers to B and B refers to A), raise a ValueError.
• If a placeholder references a key that does not exist in mapping, raise a KeyError.

Return the fully expanded string.

Function Signature

def expand_template(template: str, mapping: dict[str, str]) -> str:
    pass

Constraints

• 0 <= len(template) <= 10^4
• 0 <= len(mapping) <= 1000
• Keys in mapping consist of [A-Za-z0-9_]+
• All strings consist of printable ASCII characters

Examples

Example 1

template = "I am %USER%. My home is %HOME%."
mapping = {
    "USER": "admin",
    "HOME": "/%USER%/home"
}
output = expand_template(template, mapping)
# Result: "I am admin. My home is /admin/home."

Explanation: %USER% expands to "admin". %HOME% expands to "/%USER%/home", which recursively resolves to "/admin/home".

Example 2

template = "Usage: 100%% completed by %USER%"
mapping = {
    "USER": "alice"
}
output = expand_template(template, mapping)
# Result: "Usage: 100% completed by alice"

Explanation: %% is escaped to a single literal %.

Example 3 (Cycle)

template = "Config: %A%"
mapping = {
    "A": "%B%",
    "B": "%A%"
}
# Raises ValueError: Circular dependency detected

Edge Cases to Consider

• Unmatched or single % characters that do not form a valid placeholder should be treated as literal text.
• Deeply nested or chain-like expansions (e.g., A -> B -> C -> ... -> Z).
• Repeated references to the same key; expansion should avoid redundant work through memoization.