LeetCode 833: Find And Replace in String

Problem Restatement

We are given a string s and three arrays:

For each operation i, we check whether sources[i] appears in the original string s starting at index indices[i].

If it matches, we replace that source substring with targets[i].

If it does not match, we do nothing.

All replacements happen simultaneously, so every index refers to the original string, not a modified string. The test cases guarantee that replacements do not overlap.

Input and Output

Function shape:

class Solution:
    def findReplaceString(
        self,
        s: str,
        indices: list[int],
        sources: list[str],
        targets: list[str],
    ) -> str:
        ...

Examples

Example 1:

s = "abcd"
indices = [0, 2]
sources = ["a", "cd"]
targets = ["eee", "ffff"]

Check the first operation:

s[0:] starts with "a"

So replace "a" with "eee".

Check the second operation:

s[2:] starts with "cd"

So replace "cd" with "ffff".

The result is:

"eeebffff"

Example 2:

s = "abcd"
indices = [0, 2]
sources = ["ab", "ec"]
targets = ["eee", "ffff"]

Check the first operation:

s[0:] starts with "ab"

So replace "ab" with "eee".

Check the second operation:

s[2:] does not start with "ec"

So we do nothing for that operation.

The result is:

"eeecd"

First Thought: Apply Replacements One by One

A tempting approach is to modify the string immediately for each replacement operation.

class Solution:
    def findReplaceString(
        self,
        s: str,
        indices: list[int],
        sources: list[str],
        targets: list[str],
    ) -> str:
        for index, source, target in zip(indices, sources, targets):
            if s.startswith(source, index):
                s = s[:index] + target + s[index + len(source):]

        return s

This can be wrong because replacements are simultaneous.

After one replacement changes the length of the string, later indices may no longer refer to the same positions.

The problem says every indices[i] refers to the original string.

Key Insight

We should not modify s while checking replacements.

Instead:

1. First decide which original indices have valid replacements.
2. Then build the final string from left to right.

Use a replacement map:

replace_at[index] = operation_index

This tells us that when we reach index in the original string, we should append targets[operation_index] and skip the source substring.

Algorithm

Create an array replace_at of length len(s) initialized with -1.

For each operation op:

1. Let start = indices[op].
2. Let source = sources[op].
3. Check whether s.startswith(source, start).
4. If yes, set:

replace_at[start] = op

Then build the answer:

1. Start at i = 0.
2. If replace_at[i] != -1, append the corresponding target.
3. Skip forward by the length of the corresponding source.
4. Otherwise, append s[i] and move forward by 1.

Walkthrough

Use:

s = "abcd"
indices = [0, 2]
sources = ["a", "cd"]
targets = ["eee", "ffff"]

First create:

replace_at = [-1, -1, -1, -1]

Operation 0:

index = 0
source = "a"

It matches, so:

replace_at[0] = 0

Now:

replace_at = [0, -1, -1, -1]

Operation 1:

index = 2
source = "cd"

It matches, so:

replace_at[2] = 1

Now:

replace_at = [0, -1, 1, -1]

Build the result.

At i = 0, there is replacement operation 0.

Append:

"eee"

Skip length of "a", so i = 1.

At i = 1, no replacement.

Append:

"b"

At i = 2, there is replacement operation 1.

Append:

"ffff"

Skip length of "cd", so the scan ends.

Result:

"eeebffff"

Correctness

The first pass checks each replacement against the original string s.

Therefore, whether an operation is valid is decided using the correct original indices.

For every valid replacement, the algorithm records the operation only at its original start index.

During the second pass, the algorithm scans the original string from left to right.

If no replacement starts at position i, the character s[i] must appear unchanged in the final string, so the algorithm appends it.

If a valid replacement starts at position i, the source substring beginning at i must be replaced by its target. The algorithm appends that target and skips exactly the length of the source substring.

Because valid replacements do not overlap, skipping the source substring cannot skip another valid replacement that should also be applied.

Thus every original character is either copied once or belongs to exactly one replaced source substring. Every valid replacement is applied exactly once. Therefore, the final string is correct.

Complexity

Here n = len(s).

In Python, s.startswith(source, start) checks the relevant source length, so all match checks together cost proportional to the total length of checked sources.

Implementation

class Solution:
    def findReplaceString(
        self,
        s: str,
        indices: list[int],
        sources: list[str],
        targets: list[str],
    ) -> str:
        n = len(s)
        replace_at = [-1] * n

        for op, start in enumerate(indices):
            source = sources[op]

            if s.startswith(source, start):
                replace_at[start] = op

        result = []
        i = 0

        while i < n:
            op = replace_at[i]

            if op != -1:
                result.append(targets[op])
                i += len(sources[op])
            else:
                result.append(s[i])
                i += 1

        return "".join(result)

Code Explanation

We create a lookup array:

replace_at = [-1] * n

A value of -1 means no replacement starts at that index.

For each operation, we check whether the source really matches the original string:

if s.startswith(source, start):
    replace_at[start] = op

Then we build the result:

result = []
i = 0

If a replacement starts at i:

result.append(targets[op])
i += len(sources[op])

We append the target and skip the source substring in the original string.

Otherwise:

result.append(s[i])
i += 1

We copy the current character unchanged.

Finally:

return "".join(result)

joins all pieces into the final string.

Testing

def run_tests():
    s = Solution()

    assert s.findReplaceString(
        "abcd",
        [0, 2],
        ["a", "cd"],
        ["eee", "ffff"],
    ) == "eeebffff"

    assert s.findReplaceString(
        "abcd",
        [0, 2],
        ["ab", "ec"],
        ["eee", "ffff"],
    ) == "eeecd"

    assert s.findReplaceString(
        "abcdxyz",
        [4, 0],
        ["x", "ab"],
        ["Q", "12"],
    ) == "12cdQyz"

    assert s.findReplaceString(
        "abc",
        [0, 1],
        ["x", "y"],
        ["p", "q"],
    ) == "abc"

    assert s.findReplaceString(
        "aaaaa",
        [0, 3],
        ["aa", "aa"],
        ["b", "c"],
    ) == "baac"

    print("all tests passed")

run_tests()

Test meaning: