515. Find And Replace in String
Your function receives a string s and k replacement operations described by three parallel arrays: indices, sources, and targets.
Operation i is conditional: if the substring sources[i] appears in s starting exactly at position indices[i], replace that occurrence with targets[i]; otherwise the operation silently does nothing. All checks are made against the original string, and the operations are applied simultaneously — the tests guarantee the matched ranges never overlap, so no two operations fight over the same characters.
Return the string after all operations have been applied. Note that targets[i] may be longer or shorter than sources[i], and the operations are not given in any particular order.
Example 1:
Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Output: "eeebffff"
Explanation: "a" occurs at index 0, so it becomes "eee". "cd" occurs at index 2, so it becomes "ffff". The untouched "b" stays in between.
Example 2:
Input: s = "abcd", indices = [0, 2], sources = ["ab", "ec"], targets = ["eee", "ffff"]
Output: "eeecd"
Explanation: "ab" matches at index 0 and becomes "eee". "ec" does NOT appear at index 2 (the string has "cd" there), so the second operation is skipped.
Constraints:
- 1 ≤ s.length ≤ 1000
- 1 ≤ k == indices.length == sources.length == targets.length ≤ 100
- 0 ≤ indices[i] < s.length
- 1 ≤ sources[i].length, targets[i].length ≤ 50
- s, sources[i], and targets[i] consist of lowercase English letters only
- The matched source ranges are guaranteed not to overlap
- All values of indices are distinct
Hints:
Replacing left-to-right shifts every later index, and the given indices refer to the original string. What order makes the indices stay valid?
Sort the operations by index descending and splice right-to-left: edits at high positions never move the characters at lower positions.
Even cleaner: build the answer left-to-right. Put the operations in a map from start index → operation; walk i through s, and at each position either emit the target and jump i past the source, or copy one character.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Expected output: "eeebffff"