Apply Substitutions

Problem

You are given a string s and a 2D string array substitutions where each substitutions[i] = [old_i, new_i] indicates that you may replace any occurrence of the non-empty substring old_i in s with new_i. You may apply each substitution any number of times.

Return the lexicographically smallest string you can obtain after applying any number of substitutions.

Examples

Example 1:

Input: s = "abba", substitutions = [["ab","ba"],["ba","ab"]]
Output: "aabb"
Explanation: We can apply the first substitution to get "bbaa", then the second to get "aabb". "aabb" is the lex smallest string possible.

Example 2:

Input: s = "leetcode", substitutions = [["leet","code"],["code","leet"]]
Output: "codecode"
Explanation: "leetcode" -> "codecode" (apply first substitution), which is the smallest possible.

---

Constraints

• 1 <= s.length <= 10^4
• 1 <= substitutions.length <= 10^4
• 1 <= old_i.length, new_i.length <= 10
• s and all strings in substitutions consist of lowercase English letters.

Solution

Method 1 - Topological Sort + BFS (Lexicographical Minimization)

Intuition

The substitutions can form cycles (e.g., ab <-> ba), so we need to find the lexicographically smallest string reachable by repeatedly applying any substitution. This is similar to finding the smallest string in a graph of possible transformations.

Approach

1. Model the substitutions as a directed graph where each node is a string, and edges represent valid substitutions.
2. Use BFS to explore all reachable strings from the initial string, always expanding the lexicographically smallest string first (using a min-heap/priority queue).
3. Track visited strings to avoid cycles and redundant work.
4. Return the smallest string found when the queue is empty.

Code

C++

#include <string>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

string applySubstitutions(string s, vector<vector<string>>& substitutions) {
    unordered_map<string, vector<string>> subs;
    for (auto& sub : substitutions) {
        subs[sub[0]].push_back(sub[1]);
    }
    unordered_set<string> visited;
    priority_queue<string, vector<string>, greater<string>> pq;
    pq.push(s);
    string result = s;
    while (!pq.empty()) {
        string curr = pq.top(); pq.pop();
        if (!visited.insert(curr).second) continue;
        result = min(result, curr);
        for (auto& [oldstr, newlist] : subs) {
            size_t pos = curr.find(oldstr);
            while (pos != string::npos) {
                for (auto& newstr : newlist) {
                    string next = curr;
                    next.replace(pos, oldstr.size(), newstr);
                    if (!visited.count(next)) {
                        pq.push(next);
                    }
                }
                pos = curr.find(oldstr, pos + 1);
            }
        }
    }
    return result;
}

Java

import java.util.*;
class Solution {
    public String applySubstitutions(String s, List<List<String>> substitutions) {
        Map<String, List<String>> subs = new HashMap<>();
        for (List<String> sub : substitutions) {
            subs.computeIfAbsent(sub.get(0), k -> new ArrayList<>()).add(sub.get(1));
        }
        Set<String> visited = new HashSet<>();
        PriorityQueue<String> pq = new PriorityQueue<>();
        pq.add(s);
        String result = s;
        while (!pq.isEmpty()) {
            String curr = pq.poll();
            if (!visited.add(curr)) continue;
            result = result.compareTo(curr) > 0 ? curr : result;
            for (String oldstr : subs.keySet()) {
                int pos = curr.indexOf(oldstr);
                while (pos != -1) {
                    for (String newstr : subs.get(oldstr)) {
                        String next = curr.substring(0, pos) + newstr + curr.substring(pos + oldstr.length());
                        if (!visited.contains(next)) {
                            pq.add(next);
                        }
                    }
                    pos = curr.indexOf(oldstr, pos + 1);
                }
            }
        }
        return result;
    }
}

Python

import heapq
from collections import defaultdict
def apply_substitutions(s, substitutions):
    subs = defaultdict(list)
    for old, new in substitutions:
        subs[old].append(new)
    visited = set()
    heap = [s]
    result = s
    while heap:
        curr = heapq.heappop(heap)
        if curr in visited:
            continue
        visited.add(curr)
        result = min(result, curr)
        for old, newlist in subs.items():
            pos = curr.find(old)
            while pos != -1:
                for new in newlist:
                    next_s = curr[:pos] + new + curr[pos+len(old):]
                    if next_s not in visited:
                        heapq.heappush(heap, next_s)
                pos = curr.find(old, pos+1)
    return result

Complexity

• ⏰ Time complexity: O(N * M * L) where N = |s|, M = number of substitutions, L = max length of old_i.
• 🧺 Space complexity: O(K) where K is the number of unique strings generated (can be exponential in worst case, but pruned by visited set).