833. Find and Replace in String

Problem Description

You are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.

To complete the ith replacement operation:

• Check if the substring sources[i] occurs at index indices[i] in the original string s.
• If it does not occur, do nothing.
• Otherwise if it does occur, replace that substring with targets[i].

For example, if s = "abcd", indices[i] = 0, sources[i] = "ab", and targets[i] = "eee", then the result of this replacement will be "eeecd".

All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.

Return the resulting string after performing all replacement operations on s.

Examples:

Input: s = "abcd", indices = [0, 2], sources = ["ab","cd"], targets = ["eee","ffff"]
Output: "eeeffff"
Explanation:
"ab" occurs at index 0 in "abcd", so we replace it with "eee".
"cd" occurs at index 2 in "abcd", so we replace it with "ffff".

Input: s = "abcd", indices = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation:
"ab" occurs at index 0 in "abcd", so we replace it with "eee".
"ec" does not occur at index 2 in "abcd", so we do nothing.

Constraints:

• 1 ≤ s.length ≤ 1000
• k == indices.length == sources.length == targets.length
• 1 ≤ k ≤ 100
• 0 ≤ indices[i] < s.length
• 1 ≤ sources[i].length, targets[i].length ≤ 50
• s consists of only lowercase English letters
• sources[i] and targets[i] consist of only lowercase English letters

Python Solution

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        # Create a list of tuples (index, source, target) and sort by index in reverse order
        operations = sorted(zip(indices, sources, targets), reverse=True)
        
        # Process each replacement from right to left
        for i, src, tgt in operations:
            if s[i:i+len(src)] == src:
                s = s[:i] + tgt + s[i+len(src):]
        
        return s

Implementation Notes:

• Processes replacements from right to left to avoid index shifting
• Uses string slicing for efficient substring operations
• Time complexity: O(nk), where n is the length of s and k is the number of operations
• Space complexity: O(n)

Java Solution

class Solution {
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
        int n = indices.length;
        // Create a list of operations sorted by index in descending order
        List ops = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            ops.add(new int[]{indices[i], i});
        }
        ops.sort((a, b) -> b[0] - a[0]);
        
        // Process each replacement from right to left
        for (int[] op : ops) {
            int i = op[0], j = op[1];
            String src = sources[j];
            String tgt = targets[j];
            
            if (s.substring(i, Math.min(i + src.length(), s.length())).equals(src)) {
                s = s.substring(0, i) + tgt + s.substring(i + src.length());
            }
        }
        
        return s;
    }
}

C++ Solution

class Solution {
public:
    string findReplaceString(string s, vector& indices, vector& sources, vector& targets) {
        int n = indices.size();
        vector> ops;
        for (int i = 0; i < n; i++) {
            ops.push_back({indices[i], i});
        }
        sort(ops.rbegin(), ops.rend());
        
        for (auto [idx, i] : ops) {
            string& src = sources[i];
            string& tgt = targets[i];
            
            if (s.substr(idx, src.length()) == src) {
                s.replace(idx, src.length(), tgt);
            }
        }
        
        return s;
    }
};

JavaScript Solution

/**
 * @param {string} s
 * @param {number[]} indices
 * @param {string[]} sources
 * @param {string[]} targets
 * @return {string}
 */
var findReplaceString = function(s, indices, sources, targets) {
    // Create operations array with indices and sort in descending order
    const ops = indices.map((idx, i) => [idx, i])
                      .sort((a, b) => b[0] - a[0]);
    
    // Process each replacement from right to left
    for (const [idx, i] of ops) {
        const src = sources[i];
        const tgt = targets[i];
        
        if (s.slice(idx, idx + src.length) === src) {
            s = s.slice(0, idx) + tgt + s.slice(idx + src.length);
        }
    }
    
    return s;
};

C# Solution

public class Solution {
    public string FindReplaceString(string s, int[] indices, string[] sources, string[] targets) {
        int n = indices.Length;
        var ops = new List<(int index, int i)>();
        for (int i = 0; i < n; i++) {
            ops.Add((indices[i], i));
        }
        ops.Sort((a, b) => b.index.CompareTo(a.index));
        
        foreach (var (idx, i) in ops) {
            string src = sources[i];
            string tgt = targets[i];
            
            if (idx + src.Length <= s.Length && 
                s.Substring(idx, src.Length) == src) {
                s = s.Substring(0, idx) + tgt + s.Substring(idx + src.Length);
            }
        }
        
        return s;
    }
}

Implementation Notes:

• Uses tuples for operation tracking
• Processes replacements in descending order of indices
• Time complexity: O(nk)
• Space complexity: O(n)