> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Find And Replace in String Python Solution

> Tested Python solution for LeetCode 833 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 833, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [String](/catalog/topics/string), [Sorting](/catalog/topics/sorting). [View on LeetCode](https://leetcode.com/problems/find-and-replace-in-string/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 833   # by problem number
lcpy gen -s find_and_replace_in_string   # by problem name
```

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

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

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/06/12/833-ex1.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.leetcode.com/uploads/2021/06/12/833-ex2-1.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 \<= indices\[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.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_and_replace_in_string/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_and_replace_in_string/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n + sum(len(sources[i]) + len(targets[i])))
    # Space: O(n)
    def find_replace_string(
        self, s: str, indices: list[int], sources: list[str], targets: list[str]
    ) -> str:
        match_at: dict[int, int] = {}
        for i, idx in enumerate(indices):
            if s.startswith(sources[i], idx):
                match_at[idx] = i

        pieces: list[str] = []
        i = 0
        while i < len(s):
            j = match_at.get(i)
            if j is None:
                pieces.append(s[i])
                i += 1
            else:
                pieces.append(targets[j])
                i += len(sources[j])
        return "".join(pieces)
```

## Complexity

| Time | Space |
| - | - |
| O(n + sum(len(sources\[i]) + len(targets\[i]))) | O(n) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.