Find And Replace in String
MedPrompt
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 indexindices[i]in the original strings. - 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.
- For example, a testcase with
s = "abc",indices = [0, 1], andsources = ["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 <= 50sconsists of only lowercase English letters.sources[i]andtargets[i]consist of only lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This is a straightforward brute-force approach. We iterate through the input string s with a pointer. At each position, we loop through all k available operations to see if one applies. If a matching operation is found, we perform the replacement and advance our pointer accordingly. Otherwise, we copy the character and advance the pointer by one.
Algorithm
- Initialize a
StringBuilderto build the result string. - Initialize a pointer
i = 0to traverse the input strings. - Loop while
iis less than the length ofs. - Inside the loop, search for a matching operation at index
i. Initialize a flagmatchFound = false. - Iterate from
j = 0tok-1:- If
indices[j] == iands.startsWith(sources[j], i):- Append
targets[j]to theStringBuilder. - Advance
ibysources[j].length(). - Set
matchFound = trueand break the inner loop (since replacements are non-overlapping).
- Append
- If
- If
matchFoundis false after checking all operations, it means no replacement starts ati.- Append
s.charAt(i)to theStringBuilder. - Increment
iby 1.
- Append
- After the main loop finishes, convert the
StringBuilderto a string and return it.
Walkthrough
class Solution { public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) { StringBuilder result = new StringBuilder(); int k = indices.length; int i = 0; while (i < s.length()) { boolean replaced = false; for (int j = 0; j < k; j++) { // Check if an operation starts at the current index i and the source matches if (indices[j] == i && s.startsWith(sources[j], i)) { result.append(targets[j]); i += sources[j].length(); replaced = true; break; // Non-overlapping, so we can break after finding one match } } if (!replaced) { result.append(s.charAt(i)); i++; } } return result.toString(); }}Complexity
Time
O(N * K * L_s), where `N` is the length of `s`, `K` is the number of operations, and `L_s` is the maximum length of a source string. The outer loop runs up to `N` times. In each iteration, we may loop through all `K` operations, and for each, `startsWith` takes `O(L_s)` time.
Space
O(L_res), where `L_res` is the length of the resulting string. This space is primarily used by the `StringBuilder` to construct the output.
Trade-offs
Pros
Simple logic, easy to understand and implement.
Minimal auxiliary space besides the result builder.
Cons
Inefficient due to the nested loop structure, leading to a high time complexity, especially for large
NandK.
This approach improves upon the brute-force method by pre-processing the replacements. First, we identify all valid replacements. Then, we sort these valid replacements by their starting index. This allows us to build the final string in a single pass over the sorted replacements, appending the original string segments that lie between the replacement points.
Algorithm
- Create a list to store valid replacement operations.
- Iterate through the
koperations. For each operationi, check ifs.startsWith(sources[i], indices[i]). - If it's a match, create an object or tuple containing the index, source length, and target string, e.g.,
(indices[i], sources[i].length(), targets[i]), and add it to the list of valid replacements. - Sort the list of valid replacements based on the index in ascending order.
- Initialize a
StringBuilderfor the result and a pointerlastIdx = 0. - Iterate through the sorted list of valid replacements:
- For each replacement
(idx, srcLen, tgt):- Append the original substring between the last replacement and the current one:
result.append(s.substring(lastIdx, idx)). - Append the target string:
result.append(tgt). - Update
lastIdx = idx + srcLen.
- Append the original substring between the last replacement and the current one:
- For each replacement
- After the loop, append any remaining part of the original string:
result.append(s.substring(lastIdx)). - Return the string from the
StringBuilder.
Walkthrough
To implement this, we can define a helper class Replacement to store the details of each valid operation. After filtering and sorting, we iterate through the sorted list, building the result string piece by piece.
class Solution { class Replacement { int index; int sourceLength; String target; Replacement(int index, int sourceLength, String target) { this.index = index; this.sourceLength = sourceLength; this.target = target; } } public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) { List<Replacement> validReplacements = new ArrayList<>(); for (int i = 0; i < indices.length; i++) { if (s.startsWith(sources[i], indices[i])) { validReplacements.add(new Replacement(indices[i], sources[i].length(), targets[i])); } } // Sort replacements by their start index Collections.sort(validReplacements, (a, b) -> a.index - b.index); StringBuilder result = new StringBuilder(); int lastIndex = 0; for (Replacement rep : validReplacements) { // Append the segment of the original string before the current replacement result.append(s.substring(lastIndex, rep.index)); // Append the target string for the replacement result.append(rep.target); // Update the last index to be after the replaced source string lastIndex = rep.index + rep.sourceLength; } // Append the final segment of the original string result.append(s.substring(lastIndex)); return result.toString(); }}Complexity
Time
O(K*L_s + K log K + N). It takes `O(K*L_s)` to find all valid replacements. Sorting these `K` (at most) replacements takes `O(K log K)`. Building the final string involves iterating through the replacements and creating substrings, which in total takes `O(N + L_T)`, where `L_T` is the total length of targets. This can be simplified to `O(N)` as the total length of substrings from `s` is `N`.
Space
O(K + L_res), where `K` is the number of operations and `L_res` is the length of the result string. `O(K)` space is needed to store the valid replacements, and `O(L_res)` for the result `StringBuilder`.
Trade-offs
Pros
Much more efficient than the brute-force approach.
The logic is clean and easy to follow once the replacements are filtered and sorted.
Cons
Requires sorting, which adds a
O(K log K)factor to the time complexity.Uses
O(K)extra space to store the valid replacements.
This is the most time-efficient approach. It avoids sorting by using a direct mapping data structure (an array in this case, since indices are bounded) to store replacement information. We make one pass to populate this map with valid operations and a second pass over the string to build the result, using the map for quick lookups.
Algorithm
- Create an array, let's call it
op_map, of sizes.length(), and initialize all its elements with a sentinel value (e.g., -1). This array will map a start index insto the index of the operation in the original input arrays. - Iterate from
i = 0tok-1:- Check if
s.startsWith(sources[i], indices[i]). - If it matches, store the operation index
iatop_map[indices[i]].
- Check if
- Initialize a
StringBuilderfor the result and a pointeri = 0to traverses. - Loop while
i < s.length():- If
op_map[i]is not the sentinel value, it means a valid replacement starts ati.- Get the operation index
op_idx = op_map[i]. - Append
targets[op_idx]to the result. - Advance the pointer
ibysources[op_idx].length().
- Get the operation index
- Otherwise, no replacement starts at
i.- Append
s.charAt(i)to the result. - Increment
iby 1.
- Append
- If
- Return the string from the
StringBuilder.
Walkthrough
The core idea is to trade space for time. By using an array of the same size as the input string, we can mark which operations are valid and where they start. This eliminates the need for sorting or repeated checks.
import java.util.Arrays; class Solution { public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) { int n = s.length(); int k = indices.length(); int[] op_map = new int[n]; Arrays.fill(op_map, -1); // First pass: check for valid operations and map their start index to their original index for (int i = 0; i < k; i++) { if (s.startsWith(sources[i], indices[i])) { op_map[indices[i]] = i; } } StringBuilder result = new StringBuilder(); int i = 0; // Second pass: build the result string while (i < n) { if (op_map[i] != -1) { // A valid replacement starts here int op_idx = op_map[i]; result.append(targets[op_idx]); i += sources[op_idx].length(); } else { // No replacement, just append the original character result.append(s.charAt(i)); i++; } } return result.toString(); }}Complexity
Time
O(N + K*L_s). The first pass to populate the `op_map` takes `O(K*L_s)`. The second pass to build the string takes `O(N + L_T)` (where `L_T` is the total length of targets), as each character of `s` or its replacement is processed once. This simplifies to `O(N)` for the traversal part. The total complexity is the sum of these two parts.
Space
O(N + L_res). `O(N)` for the `op_map` array and `O(L_res)` for the result `StringBuilder`, where `L_res` is the length of the result string.
Trade-offs
Pros
Most time-efficient as it avoids the
O(K log K)sorting step.The logic is straightforward with two distinct passes over the data.
Cons
Uses more auxiliary space (
O(N)) than the sorting approach (O(K)), which could be a factor ifNis much larger thanK.
Solutions
Solution
class Solution {public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) { int n = s.length(); var d = new int[n]; Arrays.fill(d, -1); for (int k = 0; k < indices.length; ++k) { int i = indices[k]; if (s.startsWith(sources[k], i)) { d[i] = k; } } var ans = new StringBuilder(); for (int i = 0; i < n;) { if (d[i] >= 0) { ans.append(targets[d[i]]); i += sources[d[i]].length(); } else { ans.append(s.charAt(i++)); } } return ans.toString(); }}class Solution {public: string findReplaceString(string s, vector<int> &indices, vector<string> &sources, vector<string> &targets) { int n = s.size(); vector<int> d(n, -1); for (int k = 0; k < indices.size(); ++k) { int i = indices[k]; if (s.compare(i, sources[k].size(), sources[k]) == 0) { d[i] = k; } } string ans; for (int i = 0; i < n;) { if (~d[i]) { ans += targets[d[i]]; i += sources[d[i]].size(); } else { ans += s[i++]; } } return ans; }};class Solution: def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str: n = len(s) d = [- 1] * n for k, (i, src) in enumerate(zip(indices, sources)): if s . startswith(src, i): d[i] = k ans = [] i = 0 while i < n: if ~ d[i]: ans . append(targets[d[i]]) i += len(sources[d[i]]) else: ans . append(s[i]) i += 1 return "" . join(ans)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.