Apply Substitutions - Solution & Explanation

Problem Overview: You receive a set of substitution rules where a key maps to a string that may reference other keys. Applying substitutions requires expanding each key until only final characters remain. Dependencies between keys form a directed graph, so the main challenge is resolving them in the correct order while avoiding repeated work.

Approach 1: Hash Table + Recursion (DFS with Memoization) (Time: O(n + L), Space: O(n + L))

Store every substitution rule in a hash table so you can resolve a key in constant time. When expanding a key, recursively resolve every referenced token inside its string. This naturally forms a graph where nodes are variables and edges represent dependencies. A depth‑first traversal expands dependencies first, then builds the final resolved string for the current key.

Memoization prevents recomputing the same substitution multiple times. Once a key is fully expanded, cache the result in the hash map. Future lookups return instantly. This converts repeated expansions from exponential behavior into linear work relative to the total size of all strings.

Cycle detection is handled with a recursion stack or visiting set. If a key is encountered while it is still being processed, the rules contain a circular dependency. In most implementations you either reject the input or skip further expansion. Because each key is processed once and each character is appended once, the runtime stays O(n + L), where n is the number of rules and L is the total length of all expanded strings.

Approach 2: Graph + Topological Sort (Time: O(n + L), Space: O(n + L))

You can model the substitutions explicitly as a dependency graph and resolve them in topological order. First build adjacency lists showing which keys depend on which other keys. Then compute in‑degrees and run a BFS‑style topological sort. Keys with no dependencies resolve immediately because their substitution strings contain only literals.

As each node is processed, replace references in dependent nodes with the resolved value and reduce their in‑degree. Once a dependent node has no remaining unresolved references, it becomes eligible for processing. This approach avoids recursion and works well when the dependency graph is large or when iterative solutions are preferred.

Recommended for interviews: The Hash Table + DFS approach is typically expected. It is concise, naturally expresses dependency resolution, and shows familiarity with memoization and graph traversal. Mentioning the topological sort alternative demonstrates deeper understanding of dependency graphs and how DFS and BFS can both solve the same problem.