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:
sources[i] occurs at index indices[i] in the original string s.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.
s = "abc", indices = [0, 1], and sources = ["ab","bc"] will not be generated because the "ab" and "bc" replacements overlap.Return the resulting string after performing all replacement operations on s.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"] Output: "eeebffff" Explanation: "a" occurs at index 0 in s, so we replace it with "eee". "cd" occurs at index 2 in s, so we replace it with "ffff".
Example 2:
Input: s = "abcd", indices = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"] Output: "eeecd" Explanation: "ab" occurs at index 0 in s, so we replace it with "eee". "ec" does not occur at index 2 in s, so we do nothing.
Constraints:
1 <= s.length <= 1000k == indices.length == sources.length == targets.length1 <= k <= 1000 <= indexes[i] < s.length1 <= sources[i].length, targets[i].length <= 50s consists of only lowercase English letters.sources[i] and targets[i] consist of only lowercase English letters.Problem Overview: You receive a base string s and three arrays: indices, sources, and targets. For each index i, replace the substring starting at indices[i] with targets[i] only if the substring exactly matches sources[i]. All replacements must behave as if they occur simultaneously.
Approach 1: Simultaneous Replacement using Sorting (O(n + k log k) time, O(n) space)
This approach sorts replacement operations by their starting index so you can scan the string from left to right while applying valid replacements. Pair each index with its corresponding source and target, then sort the pairs by index. While iterating through s, check whether the current position matches the next replacement index. If the substring s[index:index+len(source)] equals the source, append the target to the result and skip ahead by the source length. Otherwise, copy the current character and continue. Sorting ensures replacements are processed in order, preventing conflicts and maintaining the “simultaneous” requirement. This technique mainly uses sequential traversal of the string combined with ordered processing through sorting. Time complexity is O(n + k log k) where k is the number of replacements, and space complexity is O(n) for the result builder.
Approach 2: Direct Index Mapping (O(n) time, O(n) space)
A faster strategy builds a direct lookup structure mapping each replacement index to its operation. Create a dictionary or array where map[index] stores the corresponding source and target. Then iterate through the string once. At each position i, check if a replacement begins there using a constant-time hash lookup. If present, verify that the substring matches the source; if it does, append the target and jump forward by the source length. Otherwise append the current character and move forward by one. This eliminates the sorting step and relies on efficient hash table lookups and linear traversal of the array of indices. The algorithm runs in O(n) time with O(n) additional space for the result and mapping.
Recommended for interviews: The direct index mapping approach is typically expected because it achieves linear time with a clean single pass. The sorting approach still demonstrates solid reasoning about ordered operations and is easier to derive during an interview. Showing both communicates strong understanding: sorting proves you can structure the operations correctly, while index mapping shows optimization using hash-based lookup.
Sort replacement operations based on indices to ensure they are handled in the correct order. This method involves performing a right-to-left replacement such that indices remain unaffected.
This C solution leverages sorting to handle replacements from right to left, ensuring index integrity. A custom structure holds replacement details and a qsort function sorts them based on indices in descending order. After sorting, the program performs replacements where valid, preserving the order of operations.
Time Complexity: O((k + m) log k) where m is the maximum mismatch length.
Space Complexity: O(n + k) where n is the length of the given string.
Utilize an array to directly map changes to their respective indices. This way, valid operations can be done directly on the array without affecting others.
Utilizing a list to represent the string avoids mutability issues. Each valid replacement modifies the list directly, keeping replacements straightforward and simultaneous.
Python
JavaScript
Java
Time Complexity: O(n*k) worst case as each replacement traverses through the string length.
Space Complexity: O(n), determined by the additional list copy of the input string.
We iterate through each replacement operation. For the current k-th replacement operation (i, src), if s[i..i+|src|-1] is equal to src, we record that the string at index i needs to be replaced with the k-th string in targets; otherwise, no replacement is needed.
Next, we only need to iterate through the original string s and perform the replacements based on the recorded information.
The time complexity is O(L), and the space complexity is O(n), where L is the sum of the lengths of all strings, and n is the length of the string s.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Simultaneous Replacement using Sorting | Time Complexity: O((k + m) log k) where m is the maximum mismatch length. |
| Approach 2: Direct Index Mapping | Time Complexity: O(n*k) worst case as each replacement traverses through the string length. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simultaneous Replacement using Sorting | O(n + k log k) | O(n) | When operations must be processed in order and you want a straightforward implementation. |
| Direct Index Mapping | O(n) | O(n) | Best general solution; avoids sorting and performs replacements in a single pass. |
Find and Replace in String | GeeksforGeeks Problem of the Day • Code with Alisha • 14,590 views views
Watch 8 more video solutions →Practice Find And Replace in String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor