Is Apply Substitutions easy or hard?

Apply Substitutions is generally considered a medium difficulty problem. The tricky part is recognizing that substitution rules create a dependency graph and that memoized DFS or topological sorting efficiently resolves the chain.

Apply Substitutions Python/Java solution

Python, Java, C++, Go, and TypeScript implementations typically use a dictionary or map plus a recursive DFS function. The DFS resolves dependencies and stores computed results in a memo map to avoid repeated expansion.

How to solve Apply Substitutions in O(n)?

Build a hash map from variable to substitution string, then run DFS to expand each variable. During recursion, resolve referenced variables first and cache their results. Because each variable and character is processed once, the total runtime becomes O(n + L).

What is the best approach for Apply Substitutions?

The most practical approach uses a hash table with DFS recursion and memoization. Each substitution rule becomes a node in a dependency graph, and DFS resolves dependencies before building the final string. Memoization ensures every key is expanded only once, giving O(n + L) time where L is the total expanded string length.

Is Apply Substitutions asked at Google/Amazon/Meta?

Dependency resolution and substitution expansion problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often test graph modeling, cycle detection, and DFS with memoization.

What data structure is used in Apply Substitutions?

The core structure is a hash table mapping each variable to its substitution string. Internally the relationships form a directed graph, which is traversed using depth‑first search or resolved using topological sorting.

What is the time complexity of Apply Substitutions?

The optimal solution runs in O(n + L) time. Each substitution rule is processed once and every character in the final expanded strings is appended once. Memoization prevents repeated recomputation of previously resolved keys.

Description Hints 2 Solution Video 18:50

3481. Apply Substitutions

Medium78.0% acceptance1 companyPremium elsewhere, free here

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.

Return the fully substituted text string which does not contain any placeholders.

Example 1:

Input: replacements = [["A","abc"],["B","def"]], text = "%A%_%B%"

Output: "abc_def"

Explanation:

The mapping associates "A" with "abc" and "B" with "def".
Replace %A% with "abc" and %B% with "def" in the text.
The final text becomes "abc_def".

Example 2:

Input: replacements = [["A","bce"],["B","ace"],["C","abc%B%"]], text = "%A%_%B%_%C%"

Output: "bce_ace_abcace"

Explanation:

The mapping associates "A" with "bce", "B" with "ace", and "C" with "abc%B%".
Replace %A% with "bce" and %B% with "ace" in the text.
Then, for %C%, substitute %B% in "abc%B%" with "ace" to obtain "abcace".
The final text becomes "bce_ace_abcace".

Constraints:

1 <= replacements.length <= 10
Each element of replacements is a two-element list [key, value], where:
- key is a single uppercase English letter.
- value is a non-empty string of at most 8 characters that may contain zero or more placeholders formatted as %<key>%.
All replacement keys are unique.
The text string is formed by concatenating all key placeholders (formatted as %<key>%) randomly from the replacements mapping, separated by underscores.
text.length == 4 * replacements.length - 1
Every placeholder in the text or in any replacement value corresponds to a key in the replacements mapping.
There are no cyclic dependencies between replacement keys.

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Build a dependency graph where each key is a node, and add an edge from key X to key Y if the replacement value for Y contains the placeholder %X%. Then perform a topological sort to determine a valid order for substitution.

Hint 2

Process the keys in the topologically sorted order by replacing placeholders in each replacement value with its fully expanded value. Finally, substitute the placeholders in the text using these computed values.

18:50

Still stuck?Read the written solution, or watch a walkthrough.

Open solution