Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Solution

LeetCode 3481 - Apply Substitutions

Problem Understanding

This problem gives us a collection of replacement rules and a text containing placeholders. Every placeholder has the format %X%, where X is a single uppercase letter corresponding to one of the replacement keys.

The important detail is that replacement values may themselves contain placeholders. Therefore, a replacement cannot always be performed in a single pass. Some values depend on other values, which may depend on still other values.

For example, if:

A -> "hello"
B -> "%A% world"

then %B% does not directly expand to a final string. We must first resolve %A% inside B, producing "hello world".

The input consists of:

replacements, a list of [key, value] pairs.
text, a string containing placeholders.

The output should be the fully expanded version of text, with every placeholder recursively replaced until no placeholders remain.

The constraints provide several useful guarantees:

There are at most 10 replacement keys.
Keys are single uppercase letters.
Every referenced placeholder corresponds to a valid key.
There are no cyclic dependencies.
Replacement strings are short.

The absence of cycles is especially important. It guarantees that recursive expansion will eventually terminate. Without this guarantee, a definition such as:

A -> "%B%"
B -> "%A%"

would create an infinite loop.

Some important edge cases include replacement chains several levels deep, replacement values containing multiple placeholders, replacement values with no placeholders at all, and multiple references to the same key. The problem guarantees that every placeholder can be resolved and that no cyclic dependency exists.

Approaches

Brute Force

A straightforward approach is to repeatedly scan every replacement string and repeatedly substitute placeholders whenever possible.

We could keep applying replacements across all strings until no placeholder remains anywhere.

Because there are no cycles, this process eventually converges to fully expanded strings.

While correct, this approach performs unnecessary work. The same replacement may be expanded many times. If several keys depend on the same key, we repeatedly recompute identical expansions.

Key Insight

The replacement relationships form a directed acyclic graph.

If:

C -> "abc%B%"

then C depends on B.

Because the problem guarantees no cycles, each key has a well-defined fully expanded value.

Instead of repeatedly expanding everything, we can compute the final value of each key exactly once using Depth First Search with memoization.

For a key:

If it has already been expanded, return the cached result.
Otherwise, recursively expand every placeholder inside its value.
Store the fully expanded string in a memo table.
Return the result.

After all keys are resolved, we perform one final expansion of the input text.

This avoids redundant work and naturally follows the dependency structure.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(K²L)	O(KL)	Repeatedly reprocesses already expanded values
Optimal	O(KL)	O(KL)	DFS with memoization expands each key once

Here:

K = number of replacement keys
L = total length of all replacement strings after expansion

Because the constraints are tiny, either solution would pass, but the memoized DFS is the cleanest and most scalable approach.

Algorithm Walkthrough

Store all replacement pairs in a hash map from key to value.
Create a memoization hash map. Once a key has been fully expanded, store its final string here so future requests can reuse it immediately.
Define a recursive function resolve(key).
Inside resolve(key), first check whether the key already exists in the memo table. If it does, return the cached value.
Retrieve the raw replacement string associated with the key.
Scan the string from left to right.
Whenever a placeholder %X% is encountered, recursively call resolve(X) to obtain its fully expanded value.
Append ordinary characters directly to the output being built.
Append expanded placeholder values whenever placeholders are encountered.
After the entire replacement string has been processed, store the resulting fully expanded string in the memo table.
Return the expanded string.
After defining the DFS function, process the input text using the same placeholder-expansion logic.
Whenever a placeholder %X% appears in text, replace it with resolve(X).
Return the resulting fully expanded string.

Why it works

The dependency graph is acyclic. Therefore, every recursive call eventually reaches a replacement string that contains no unresolved placeholders.

The DFS computes the fully expanded value of a key only after all of its dependencies have been expanded. Memoization guarantees that each key is expanded at most once. Thus every placeholder is replaced by its correct final value, and the final text contains no placeholders.

Python Solution

from typing import List

class Solution:
    def applySubstitutions(self, replacements: List[List[str]], text: str) -> str:
        mapping = {key: value for key, value in replacements}
        memo = {}

        def expand_string(s: str) -> str:
            result = []
            i = 0

            while i < len(s):
                if s[i] == "%":
                    key = s[i + 1]
                    result.append(resolve(key))
                    i += 3
                else:
                    result.append(s[i])
                    i += 1

            return "".join(result)

        def resolve(key: str) -> str:
            if key in memo:
                return memo[key]

            expanded = expand_string(mapping[key])
            memo[key] = expanded
            return expanded

        return expand_string(text)

The solution first converts the replacement list into a hash map for constant time lookup.

The resolve() function is responsible for computing the fully expanded value of a key. Before doing any work, it checks the memo table. If the value has already been computed, it immediately returns the cached result.

The helper function expand_string() scans a string and expands every placeholder it encounters. When it sees %X%, it calls resolve(X) to obtain the fully expanded value.

Because resolve() caches results, every key is expanded only once. Finally, the original text is processed using the same expansion logic and returned as the answer.

Go Solution

func applySubstitutions(replacements [][]string, text string) string {
	mapping := make(map[byte]string)

	for _, pair := range replacements {
		mapping[pair[0][0]] = pair[1]
	}

	memo := make(map[byte]string)

	var resolve func(byte) string
	var expandString func(string) string

	expandString = func(s string) string {
		result := make([]byte, 0)

		for i := 0; i < len(s); {
			if s[i] == '%' {
				key := s[i+1]
				result = append(result, resolve(key)...)
				i += 3
			} else {
				result = append(result, s[i])
				i++
			}
		}

		return string(result)
	}

	resolve = func(key byte) string {
		if value, exists := memo[key]; exists {
			return value
		}

		expanded := expandString(mapping[key])
		memo[key] = expanded
		return expanded
	}

	return expandString(text)
}

The Go implementation follows exactly the same logic as the Python version.

The main difference is that keys are stored as byte values because each key is a single uppercase letter. A map[byte]string is therefore sufficient and slightly more efficient than using strings as keys. Memoization is implemented with another map, and recursive closures are used for both expansion functions.

Worked Examples

Example 1

Input

replacements = [
    ["A", "abc"],
    ["B", "def"]
]

text = "%A%_%B%"

Build Mapping

Key	Value
A	abc
B	def

Resolve Text

Step	Current Token	Expansion	Result
1	%A%	abc	abc
2	_	_	abc_
3	%B%	def	abc_def

Final answer:

abc_def

Example 2

Input

replacements = [
    ["A", "bce"],
    ["B", "ace"],
    ["C", "abc%B%"]
]

text = "%A%_%B%_%C%"

Build Mapping

Key	Value
A	bce
B	ace
C	abc%B%

Resolve C

Raw value:

abc%B%

Processing:

Position	Content	Output
abc	literal text	abc
%B%	resolve(B)	abcace

Memo becomes:

Key	Expanded
B	ace
C	abcace

Expand Text

Token	Expansion
%A%	bce
%B%	ace
%C%	abcace

Result:

bce_ace_abcace

Complexity Analysis

Measure	Complexity	Explanation
Time	O(KL)	Each replacement string is fully expanded once because of memoization
Space	O(KL)	Memo table stores expanded values

Let K be the number of keys and L be the total size of all expanded replacement strings. Memoization ensures each key is processed exactly once. Every character in every replacement string is examined a constant number of times, leading to linear complexity in the total expanded output size.

Test Cases

sol = Solution()

# Example 1
assert sol.applySubstitutions(
    [["A", "abc"], ["B", "def"]],
    "%A%_%B%"
) == "abc_def"

# Example 2
assert sol.applySubstitutions(
    [["A", "bce"], ["B", "ace"], ["C", "abc%B%"]],
    "%A%_%B%_%C%"
) == "bce_ace_abcace"

# Single key, no dependencies
assert sol.applySubstitutions(
    [["A", "xyz"]],
    "%A%"
) == "xyz"

# Multi-level dependency chain
assert sol.applySubstitutions(
    [["A", "x"], ["B", "%A%y"], ["C", "%B%z"]],
    "%C%"
) == "xyz"

# Multiple placeholders in one replacement
assert sol.applySubstitutions(
    [["A", "ab"], ["B", "cd"], ["C", "%A%%B%"]],
    "%C%"
) == "abcd"

# Repeated dependency references
assert sol.applySubstitutions(
    [["A", "x"], ["B", "%A%%A%%A%"]],
    "%B%"
) == "xxx"

# Deep dependency tree
assert sol.applySubstitutions(
    [
        ["A", "a"],
        ["B", "%A%b"],
        ["C", "%B%c"],
        ["D", "%C%d"]
    ],
    "%D%"
) == "abcd"

# Multiple top-level placeholders
assert sol.applySubstitutions(
    [["A", "one"], ["B", "two"]],
    "%A%_%B%_%A%"
) == "one_two_one"

# Dependency appearing in several keys
assert sol.applySubstitutions(
    [["A", "x"], ["B", "%A%y"], ["C", "%A%z"]],
    "%B%_%C%"
) == "xy_xz"

# Long chain of expansions
assert sol.applySubstitutions(
    [
        ["A", "1"],
        ["B", "%A%2"],
        ["C", "%B%3"],
        ["D", "%C%4"]
    ],
    "%D%"
) == "1234"

Test Summary

Test	Why
Example 1	Basic direct substitution
Example 2	Nested dependency resolution
Single key	Smallest valid input
Multi-level chain	Recursive expansion
Multiple placeholders	Several substitutions in one value
Repeated references	Memoization reuse
Deep dependency tree	Long dependency path
Multiple top-level placeholders	Expansion across text
Shared dependency	Same key used by multiple parents
Long chain	Stress recursive resolution

Edge Cases

Deep Dependency Chains

A replacement may depend on another replacement, which depends on another, creating a long chain such as:

D -> %C%
C -> %B%
B -> %A%
A -> x

A naive one-pass replacement would leave unresolved placeholders behind. The recursive DFS correctly follows the chain until it reaches a fully resolved value, then propagates that value back upward.

Multiple Placeholders Inside One Value

A replacement string can contain several placeholders:

C -> %A%%B%

An implementation that assumes only one placeholder per value would produce incorrect results. The scanning logic processes the entire string from left to right and expands every placeholder it encounters.

Repeated References to the Same Key

A value may reference the same key multiple times:

B -> %A%%A%%A%

Without memoization, the expansion of A could be recomputed repeatedly. The memo table guarantees that once A is expanded, all later references reuse the cached result, improving efficiency and simplifying recursive processing.

Keys With No Dependencies

Some replacement values may already be fully expanded:

A -> "hello"

The DFS handles this naturally. The scan finds no placeholders, returns the original string unchanged, stores it in the memo table, and reuses it whenever needed later.