# Find And Replace in String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-and-replace-in-string)
Canonical: https://scaleengineer.com/dsa/problems/find-and-replace-in-string
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String
---
## Problem
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:

1. Check if the **substring** `sources[i]` occurs at index `indices[i]` in the **original string** `s`.
2. If it does not occur, **do nothing**.
3. 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:**

![](https://assets.glich.co/dsa/find-and-replace-in-string/image0.png) 

**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:**

![](https://assets.glich.co/dsa/find-and-replace-in-string/image1.png) 

**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
## Brute Force: Scan String and Check Operations
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.
**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.
**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`.
### Explanation
```java
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();
    }
}
```
### 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.

## Sorting Valid Replacements
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.
**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`.
**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.
### Explanation
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.

```java
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();
    }
}
```
### Algorithm
*   Create a list to store valid replacement operations.
*   Iterate through the `k` operations. For each operation `i`, check if `s.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 `StringBuilder` for the result and a pointer `lastIdx = 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`.
*   After the loop, append any remaining part of the original string: `result.append(s.substring(lastIdx))`.
*   Return the string from the `StringBuilder`.

## Direct Mapping with an Array
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.
**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.
**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 if `N` is much larger than `K`.
### Explanation
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.

```java
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();
    }
}
```
### Algorithm
*   Create an array, let's call it `op_map`, of size `s.length()`, and initialize all its elements with a sentinel value (e.g., -1). This array will map a start index in `s` to the index of the operation in the original input arrays.
*   Iterate from `i = 0` to `k-1`:
    *   Check if `s.startsWith(sources[i], indices[i])`.
    *   If it matches, store the operation index `i` at `op_map[indices[i]]`.
*   Initialize a `StringBuilder` for the result and a pointer `i = 0` to traverse `s`.
*   Loop while `i < s.length()`:
    *   If `op_map[i]` is not the sentinel value, it means a valid replacement starts at `i`.
        *   Get the operation index `op_idx = op_map[i]`.
        *   Append `targets[op_idx]` to the result.
        *   Advance the pointer `i` by `sources[op_idx].length()`.
    *   Otherwise, no replacement starts at `i`.
        *   Append `s.charAt(i)` to the result.
        *   Increment `i` by 1.
*   Return the string from the `StringBuilder`.

# Solutions
### Java

```java
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();
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)

```