Find And Replace in String: Right-to-Left Replacement

LeetCode 833, Find And Replace in String, gives you a string s along with three parallel arrays: indices, sources, and targets. For each operation k, you check whether sources[k] appears in s starting at position indices[k]. If it does, you replace that substring with targets[k]. If it does not match, you leave the string unchanged at that position. All checks are based on the original string, and you apply all valid replacements simultaneously.

The problem

Given a string and a set of replacement operations, perform all valid replacements and return the resulting string.

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

# At index 0: s[0:1] = "a" matches sources[0], replace with "eee"
# At index 2: s[2:4] = "cd" matches sources[1], replace with "ffff"
# Result: "eeebffff"

The tricky part is not the replacement itself. It is managing the indices. When you replace "a" with "eee" at position 0, every character after position 0 shifts right by 2. That means index 2 no longer points to the right spot if you process left to right. The key insight is to process replacements from right to left. When you modify a substring at a later position, nothing to its left moves.

The solution

Sort the operations by their index in descending order, then walk through them one at a time. For each operation, verify that the source string actually appears at the given index in the original string. If it matches, splice in the target string. Since you are working from right to left, earlier indices remain valid after each replacement.

def findReplaceString(s, indices, sources, targets):
    s = list(s)
    ops = sorted(zip(indices, sources, targets), reverse=True)

    for i, src, tgt in ops:
        if s[i:i + len(src)] == list(src):
            s[i:i + len(src)] = list(tgt)

    return "".join(s)

Step-by-step walkthrough

Here is how the algorithm processes the example s = "abcd" with indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"].

By sorting in descending order and working from the end of the string backward, each replacement only affects characters at or after the current index. Characters before the current index stay exactly where they were.

Complexity analysis

Sorting the operations takes O(k log k). Converting the string to a list and performing all replacements together takes O(n) across all operations, since each character in the string is visited at most once. The total work is dominated by whichever is larger: the sort or the string traversal.

The building blocks

This problem is built from two reusable techniques that show up across many string and array modification problems.

Right-to-left modification

Whenever you need to insert or delete elements in a sequence and you have multiple modification points, processing from right to left prevents index shifting. This same idea appears in problems where you remove elements from an array by index, or in text editors that apply multiple edits to a document. The pattern is always the same: sort your operations by position descending, then apply them one by one.

Index management with parallel arrays

The problem gives you three parallel arrays that describe the same set of operations. Zipping them together and sorting by one dimension (the index) is a clean way to keep the data aligned. This pattern of "zip, sort, iterate" appears in interval scheduling, meeting room problems, and any scenario where you coordinate multiple attributes of the same logical operation.

Edge cases

Source does not match. If s[indices[k]:indices[k] + len(sources[k])] does not equal sources[k], you skip that operation entirely. The algorithm handles this naturally because the if check prevents the replacement.

Overlapping indices. The problem guarantees that no two operations overlap in the original string, so you do not need to worry about one replacement invalidating another. Each operation targets a distinct, non-overlapping region.

Empty sources or targets. If a source is an empty string, the match check s[i:i+0] == [] is always true, and the replacement inserts the target at that position. If a target is empty, the replacement effectively deletes the source substring.

Single character string. When s has length 1 and a single operation targets index 0, the algorithm works the same way. Convert to a list, check and replace, join back.

From understanding to recall

The core idea here, processing modifications from right to left, is something you can read and immediately understand. But under interview pressure, it is easy to default to left-to-right processing and then scramble to track index offsets. The detail that slips away is the sort direction: descending by index, not ascending.

Spaced repetition makes this automatic. You drill the "zip, sort descending, apply" sequence as one brick. After a few reps at increasing intervals, the right-to-left pattern is your first instinct whenever you see a problem involving multiple in-place string edits. You stop re-deriving the approach each time and start snapping together bricks you already own.

Related posts

• Find the Index of the First Occurrence in a String - A foundational string matching problem where you scan for a substring at each position
• String Compression - Another string transformation problem that uses careful index management with a read-write pointer approach
• Count and Say - An iterative string building problem where you read and transform a string one term at a time