Problem Description

Given a string S, and three arrays of the same length: indexes, sources, and targets, you are to perform a series of find-and-replace operations on S.

• For each operation, you look at the substring of S starting at indexes[i].
• If the substring matches sources[i], replace that substring with targets[i].
• All replacements are to be performed simultaneously (so that replacing one substring does not affect another).
• Each index in indexes is guaranteed to be valid and non-overlapping.
• Return the resulting string after all replacements have been applied.

Constraints: Each replacement is independent and does not interfere with others. Each operation is valid and non-overlapping, so there is only one way to perform all replacements.

Thought Process

The first step is to recognize that we need to replace substrings in the original string at specific positions, but only if the substring at that position matches a given source. Importantly, all replacements are done as if in parallel, so we can’t let one replacement interfere with another.

A brute-force approach would be to perform replacements one by one, but if we do this naively from left to right, we might invalidate the indexes for subsequent replacements. However, since replacements are non-overlapping and simultaneous, we can process the replacements in any order, as long as we avoid modifying the string in-place during iteration.

To optimize, we can use a mapping from index to the operation (source and target), and build the result string by walking through S from left to right, deciding at each position whether to replace or keep the character.

Solution Approach

Here’s a step-by-step approach to solve the problem efficiently:

1. Preprocess the operations: Build a mapping from each index to its corresponding source and target. This allows quick lookup to see if a replacement should happen at a given position.
2. Iterate through the string: Walk through S from left to right using a pointer i.
3. Check for replacement: At each position i, check if i is one of the indexes where a replacement should occur (using the mapping).
   • If yes, check if the substring at S[i:i+len(source)] matches source.
   • If it matches, append target to the result and move the pointer forward by len(source) characters.
   • If it doesn’t match or i is not in the mapping, append S[i] to the result and move forward by 1.
4. Build the result: Use a list to build the result string for efficient concatenation, then join at the end.

This approach ensures that all replacements are checked and applied simultaneously, and that we never overwrite or shift the original string during the process.

Example Walkthrough

Example Input:
S = "abcd", indexes = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]

• At index 0, check if S[0:1] == "a". Yes, so we will replace "a" with "eee".
• At index 2, check if S[2:4] == "cd". Yes, so we will replace "cd" with "ffff".

Now, process the string:

• i = 0: index 0 is in indexes and matches "a", so append "eee" and move i to 1.
• i = 1: index 1 is not in indexes, so append "b" and move i to 2.
• i = 2: index 2 is in indexes and matches "cd", so append "ffff" and move i to 4.

Time and Space Complexity

Brute-force Approach:

• For each operation, if we created a new string for each replacement, the time complexity would be O(k * n), where k is the number of operations and n is the length of S.
• Space complexity would be O(n) for each new string copy.

• We process each character in S only once, so time complexity is O(n + k * m), where m is the maximum length of a source string (for substring comparisons).
• Space complexity is O(n) for the result string and O(k) for the mapping.

In practice, since operations are sparse and non-overlapping, the optimized approach is much more efficient.

Summary

The key to solving the "Find And Replace in String" problem is to process all replacements simultaneously using a mapping from index to operation. By scanning the string from left to right and checking for replacements at each position, we avoid accidentally interfering with other operations and ensure correctness. This strategy is efficient, elegant, and leverages basic data structures for optimal performance.

Code Implementation

class Solution:
    def findReplaceString(self, S, indexes, sources, targets):
        # Map index to (source, target)
        ops = {idx: (src, tgt) for idx, src, tgt in zip(indexes, sources, targets)}
        res = []
        i = 0
        n = len(S)
        while i < n:
            if i in ops:
                src, tgt = ops[i]
                if S[i:i+len(src)] == src:
                    res.append(tgt)
                    i += len(src)
                    continue
            res.append(S[i])
            i += 1
        return ''.join(res)
      

class Solution {
public:
    string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
        unordered_map<int, pair<string, string>> ops;
        for (int i = 0; i < indexes.size(); ++i) {
            ops[indexes[i]] = {sources[i], targets[i]};
        }
        string res;
        int i = 0, n = S.size();
        while (i < n) {
            if (ops.count(i)) {
                string src = ops[i].first, tgt = ops[i].second;
                if (S.substr(i, src.size()) == src) {
                    res += tgt;
                    i += src.size();
                    continue;
                }
            }
            res += S[i];
            ++i;
        }
        return res;
    }
};
      

class Solution {
    public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
        Map<Integer, Integer> ops = new HashMap<>();
        for (int i = 0; i < indexes.length; i++) {
            ops.put(indexes[i], i);
        }
        StringBuilder res = new StringBuilder();
        int i = 0;
        while (i < S.length()) {
            if (ops.containsKey(i)) {
                int idx = ops.get(i);
                String src = sources[idx], tgt = targets[idx];
                if (S.startsWith(src, i)) {
                    res.append(tgt);
                    i += src.length();
                    continue;
                }
            }
            res.append(S.charAt(i));
            i++;
        }
        return res.toString();
    }
}
      

var findReplaceString = function(S, indexes, sources, targets) {
    const ops = {};
    for (let i = 0; i < indexes.length; i++) {
        ops[indexes[i]] = [sources[i], targets[i]];
    }
    let res = '';
    let i = 0;
    while (i < S.length) {
        if (ops.hasOwnProperty(i)) {
            let [src, tgt] = ops[i];
            if (S.substr(i, src.length) === src) {
                res += tgt;
                i += src.length;
                continue;
            }
        }
        res += S[i];
        i++;
    }
    return res;
};