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. Each replacement operation checks if a substring from sources occurs at a specified index in s and replaces it with the corresponding target if it does. All replacements must occur simultaneously.

Key Insights

• Each replacement must be checked independently based on the provided indices.
• Replacements do not affect each other's positions, meaning no overlap will occur in the replacements.
• Efficiently checking for substring matches and replacing them is crucial for performance.

Space and Time Complexity

Time Complexity: O(k * m), where k is the number of replacements and m is the maximum length of the substrings in sources. Space Complexity: O(n), where n is the length of the final string after replacements.

Solution

To solve the problem, we will:

1. Iterate through each replacement operation using the indices array.
2. For each operation, check if the substring in sources exists at the specified index in the original string s.
3. If it exists, replace that substring with the corresponding target from the targets array.
4. Use a list to construct the modified string to avoid multiple string concatenations, which can be inefficient.

Code Solutions