Fully Expand Replacement Placeholders
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
You are given `replacements`, a list of `[key, value]` pairs, and a string `text`. Each key is a unique uppercase English letter. A placeholder such as `%A%` refers to the value mapped to key `A`.
A replacement value can contain other placeholders, whose values must also be substituted. Every referenced key exists, and the replacement dependencies contain no cycles.
Return `text` after all its placeholders have been fully expanded, including placeholders inside replacement values. Keep the surrounding literal characters and the order of the text unchanged.
### C++ Interface
```cpp
class Solution {
public:
string applySubstitutions(vector<vector<string>>& replacements, string text) {
}
};
```
### Examples
**Example 1**
```text
Input: replacements = [["A","go"],["B","%A%2"],["C","%B%%A%"]], text = "%C%_%A%_%B%"
Output: "go2go_go_go2"
```
`A` expands to `go`, `B` expands to `go2`, and `C` expands to `go2go`. The text requests them in the order `C`, `A`, `B`, separated by underscores.
**Example 2**
```text
Input: replacements = [["X","q"],["Y","%X%%X%"],["Z","[%Y%]"]], text = "%Y%_%Z%_%X%"
Output: "qq_[qq]_q"
```
Both occurrences of `%X%` in `Y` contribute `q`, so `Y` becomes `qq`. Expanding `Z` preserves its brackets and produces `[qq]`.
### Constraints
- `1 <= replacements.length <= 10`.
- Every element of `replacements` is a two-element list `[key, value]`.
- Each key is one uppercase English letter, and all keys are unique.
- Each value is nonempty, has at most eight characters, and may contain zero or more placeholders formatted as `%<key>%`.
- `text` consists of all the mapping's key placeholders, each appearing once, in an arbitrary order, separated by underscores.
- `text.length == 4 * replacements.length - 1`.
- Every placeholder in `text` or a replacement value refers to a key in `replacements`.
- There are no cyclic dependencies between replacement keys.
- For this version, each replacement value and `text` is a concatenation of literal segments containing no `%` and complete, non-overlapping placeholders `%K%`, where `K` is an existing key. Every percent character belongs to one such placeholder; bare or unmatched percent signs are not valid inputs.
### Clarifying Questions
- Do the pairs have to appear in dependency order? No. A value can refer to a key listed later.
- Does using a key consume it? No. Every occurrence of its placeholder receives its fully expanded value.
- May a percent sign be literal text? No. In this version, every `%` is part of a complete placeholder; literal segments contain no percent signs.
- Should literal brackets, digits, or underscores be removed? No. Substitution changes placeholders; surrounding literal characters remain.
### What a Strong Answer Covers
- Full expansion of nested and repeated placeholder references.
- Preservation of the text's original ordering and literal characters.
- The role of the guarantees about existing keys and acyclic dependencies.
- Correct handling of expansion growth in the time and space analysis.
### Follow-up Questions
- How would the contract need to change if a replacement could refer back to itself through other keys?
- If many text strings shared the same mapping, which computed information could be reused?
```hint Resolve dependencies once
Use the acyclic dependency structure to finish a key's referenced values before finishing that key. Cache fully expanded values so repeated references do not expand the same dependency again.
```
Overview: Expand nested replacement placeholders into their complete text values while preserving literal characters and text order. Respect repeated references, existing keys, acyclic dependencies and output growth.