Generated by Codex with GPT-5

Quick facts

Problem gist

The input is a base string s and three parallel arrays:

  • indices[i] says where a possible replacement starts.
  • sources[i] says what text must already appear there.
  • targets[i] says what text to write if the source matches.

Every replacement is checked against the original string, not against a partially edited string. That “simultaneous” detail is the core of the problem. If s = "abcd", indices = [0, 2], sources = ["a", "cd"], and targets = ["eee", "ffff"], both checks happen on "abcd", so the answer is "eeebffff".

If a source does not match at its index, that operation is ignored. The challenge is to apply the successful operations without letting earlier replacements shift the positions of later checks.

Deriving the solution

The clean way to handle simultaneous replacements is to split the task into two phases.

First, inspect the original string and record only the operations whose source really appears at the requested index. This phase never modifies the string. It just builds a map from starting index to (source, target).

Second, scan s from left to right to build the answer. At each position:

  • If a recorded replacement starts here, append its target and jump forward by the length of its source.
  • Otherwise, append the original character and move forward by one.

This works because the answer is assembled from the original string positions. Replacements may have different lengths from their sources, but that no longer matters because the scan pointer moves through s, not through the growing output.

For LeetCode’s constraints, replacement ranges are non-overlapping, so a single left-to-right scan is enough. The matching pass costs O(k * m) in the worst case, where k is the number of operations and m is the maximum source length checked. Building the output costs O(n + output_length), where n is the length of s. The extra space is O(k + output_length).

Python solution

from typing import Dict, List, Tuple


Replacement = Tuple[str, str]


def matches_at(text: str, start: int, pattern: str) -> bool:
    """Return whether pattern appears in text starting exactly at start."""
    if start < 0 or start + len(pattern) > len(text):
        return False
    return text.startswith(pattern, start)


def collect_valid_replacements(
    text: str,
    indices: List[int],
    sources: List[str],
    targets: List[str],
) -> Dict[int, Replacement]:
    """Keep only replacements whose source matches the original text."""
    valid_by_index: Dict[int, Replacement] = {}

    for start, source, target in zip(indices, sources, targets):
        if matches_at(text, start, source):
            valid_by_index[start] = (source, target)

    return valid_by_index


def apply_replacements(text: str, replacements: Dict[int, Replacement]) -> str:
    """Build the final string by walking original positions left to right."""
    pieces: List[str] = []
    position = 0

    while position < len(text):
        if position in replacements:
            source, target = replacements[position]
            pieces.append(target)
            position += len(source)
        else:
            pieces.append(text[position])
            position += 1

    return "".join(pieces)


class Solution:
    def findReplaceString(
        self,
        s: str,
        indices: List[int],
        sources: List[str],
        targets: List[str],
    ) -> str:
        valid_replacements = collect_valid_replacements(
            s,
            indices,
            sources,
            targets,
        )
        return apply_replacements(s, valid_replacements)

Why this is the right shape

The main mistake candidates make is trying to edit the string in the order given by indices. That creates shifting-index bugs. After replacing "a" with "eee" at index 0, the original index 2 no longer refers to the same place in the new string.

The two-phase approach avoids that bug entirely. Matching uses the untouched input. Output construction then consumes the input once and chooses either a target string or the original character for each position.

Sorting the operations is another valid approach: validate each operation, sort by index, then append untouched gaps and targets. The index-map scan is often simpler to code because every original position is handled by the same loop.

Edge cases

If no source matches, the replacement map is empty and the scan copies every original character, so the answer is just s.

If a replacement starts at index 0 or ends at the final character, startswith plus the boundary check handles it naturally. There is no need for special casing at the edges.

If targets are shorter, longer, or empty, the scan still works because it jumps by the source length in the original string and appends the target length to the output. The output length does not control the scan pointer.

Interview follow-ups

What if the replacements could overlap?

The original LeetCode problem avoids overlapping operations, which keeps the scan straightforward. If overlaps are allowed, the interviewer must define which operation wins. Common policies are “earliest start wins”, “longest matching source wins”, or “reject conflicting input.”

For earliest-start semantics, sort valid replacements by index and skip any replacement whose start is before the current consumed position. For longest-match semantics, group matches by start index, choose the longest source at each start, and still skip later overlaps after a chosen replacement consumes a range. The complexity becomes O(k log k + total_checked_characters + output_length) because sorting or grouping is needed to make conflict handling explicit.

Can this be solved by editing from right to left?

Yes. If all operations are first validated against the original string, then applying successful replacements from larger indices to smaller indices avoids shifting the positions of not-yet-applied replacements. This is a reasonable solution in languages with efficient mutable string builders.

In Python, repeated slicing and concatenation can become expensive because each edit creates a new string. The left-to-right builder is usually cleaner and more predictable: it creates each output piece once and joins at the end.

What if there are many replacement queries on the same base string?

For one LeetCode call, checking each source with startswith is enough. If the same string receives many batches of source checks, preprocessing can help. A trie, suffix array, suffix automaton, or rolling-hash table can answer “does this source occur at this index?” faster across repeated queries.

The tradeoff is implementation complexity and memory. For interview purposes, the simple direct check is the expected answer unless the interviewer explicitly changes the scale or asks for repeated-query optimization.

How would the solution change for streaming output?

The second phase already behaves like a stream over the original string. Instead of collecting pieces, the code could yield each target or original character segment as soon as it is known. That would reduce peak memory when the caller can consume chunks incrementally.

The replacement map still needs to be known before streaming begins, because matches must be checked against the original string. If the base string itself is too large to keep in memory, the problem becomes harder: source checks at arbitrary indices require either random access to the input or a buffered stream that can hold enough lookahead to verify each source.

Takeaway

Treat simultaneous replacement as two separate problems: first decide which operations are valid against the original text, then build the result from left to right. Once those phases are separated, variable-length targets and shifting positions stop being special cases.