Find And Replace in String

Med

#0787Time: 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.

Algorithms

Sorting

Data structures

Array Hash Table String

Prompt

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 i^th 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.

For example, a testcase with 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 <= 1000
k == indices.length == sources.length == targets.length
1 <= k <= 100
0 <= indexes[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.

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 StringBuilder to build the result string.
Initialize a pointer i = 0 to traverse the input string s.
Loop while i is less than the length of s.
Inside the loop, search for a matching operation at index i. Initialize a flag matchFound = false.
Iterate from j = 0 to k-1:
- If indices[j] == i and s.startsWith(sources[j], i):
  - Append targets[j] to the StringBuilder.
  - Advance i by sources[j].length().
  - Set matchFound = true and break the inner loop (since replacements are non-overlapping).
If matchFound is false after checking all operations, it means no replacement starts at i.
- Append s.charAt(i) to the StringBuilder.
- Increment i by 1.
After the main loop finishes, convert the StringBuilder to a string and return it.

Walkthrough

1class Solution {2    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {3        StringBuilder result = new StringBuilder();4        int k = indices.length;5        int i = 0;6        while (i < s.length()) {7            boolean replaced = false;8            for (int j = 0; j < k; j++) {9                // Check if an operation starts at the current index i and the source matches10                if (indices[j] == i && s.startsWith(sources[j], i)) {11                    result.append(targets[j]);12                    i += sources[j].length();13                    replaced = true;14                    break; // Non-overlapping, so we can break after finding one match15                }16            }17            if (!replaced) {18                result.append(s.charAt(i));19                i++;20            }21        }22        return result.toString();23    }24}

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 N and K.

Solutions

Solution

1class Solution {2public3  String findReplaceString(String s, int[] indices, String[] sources,4                           String[] targets) {5    int n = s.length();6    var d = new int[n];7    Arrays.fill(d, -1);8    for (int k = 0; k < indices.length; ++k) {9      int i = indices[k];10      if (s.startsWith(sources[k], i)) {11        d[i] = k;12      }13    }14    var ans = new StringBuilder();15    for (int i = 0; i < n;) {16      if (d[i] >= 0) {17        ans.append(targets[d[i]]);18        i += sources[d[i]].length();19      } else {20        ans.append(s.charAt(i++));21      }22    }23    return ans.toString();24  }25}

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.

← Previous

Previous problem

Next problem