Problem Description

You are given a string s and need to perform k replacement operations on it. The replacements are defined by three arrays of equal length k:

• indices: the starting positions where replacements should be attempted
• sources: the substrings to look for at those positions
• targets: what to replace the source substrings with

For each replacement operation at index i:

1. Check if the substring sources[i] appears in the original string s starting at position indices[i]
2. If it matches, replace that substring with targets[i]
3. If it doesn't match, do nothing

All replacements happen simultaneously on the original string. This means:

• Replacements are independent of each other
• The position indices always refer to the original string, not any intermediate result
• The problem guarantees that replacements won't overlap

For example, with s = "abcd", if we have:

• indices[i] = 0
• sources[i] = "ab"
• targets[i] = "eee"

Since "ab" appears at index 0 in s, we replace it with "eee", resulting in "eeecd".

The task is to return the final string after applying all valid replacement operations.

Intuition

Since all replacements must happen simultaneously on the original string, we need to first identify which positions in the original string should be replaced before actually building the result. This prevents one replacement from affecting another.

The key insight is to create a mapping that tells us: "at position i in the original string, should we perform a replacement, and if so, which one?" We can use an array d of size n (length of string) where d[i] stores the index of the replacement operation to perform at position i, or -1 if no replacement should happen there.

First pass: For each replacement operation k, we check if sources[k] matches the substring starting at indices[k]. If it matches, we mark d[indices[k]] = k, indicating that at this position we should apply the k-th replacement.

Second pass: We traverse the original string from left to right. At each position i:

• If d[i] indicates a replacement (not -1), we append targets[d[i]] to our result and jump forward by the length of sources[d[i]] (since we've just replaced that entire substring)
• If no replacement is needed, we simply copy the current character and move to the next position

This two-pass approach ensures that all replacements are based on the original string positions and don't interfere with each other, while efficiently building the final result in a single traversal.

Learn more about Sorting patterns.

Solution Approach

The solution follows a two-phase approach: marking positions for replacement, then building the result string.

Phase 1: Mark Replacement Positions

We create an array d of size n (length of string s) initialized with -1 values. This array serves as a lookup table where d[i] tells us which replacement operation (if any) should be performed at position i.

d = [-1] * n
for k, (i, src) in enumerate(zip(indices, sources)):
    if s.startswith(src, i):
        d[i] = k

For each replacement operation indexed by k:

• We check if the substring sources[k] matches at position indices[k] using s.startswith(src, i)
• If it matches, we store d[indices[k]] = k, marking that the k-th replacement should occur at this position
• The ~ operator (bitwise NOT) is later used to check if d[i] is not -1, since ~(-1) = 0 which evaluates to False

Phase 2: Build the Result String

We traverse the original string and construct the result based on our marking array:

ans = []
i = 0
while i < n:
    if ~d[i]:  # if d[i] != -1
        ans.append(targets[d[i]])
        i += len(sources[d[i]])
    else:
        ans.append(s[i])
        i += 1

At each position i:

• If d[i] contains a valid replacement index (not -1), we:
  • Append the corresponding targets[d[i]] to our result
  • Skip ahead by len(sources[d[i]]) positions, as we've just replaced that entire substring
• Otherwise, we copy the current character and move to the next position

Finally, we join all parts to form the resulting string: return "".join(ans)

This approach ensures O(n) time complexity for building the result string, with the overall complexity being O(n + k×m) where k is the number of operations and m is the average length of source strings.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

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

Phase 1: Mark Replacement Positions

First, we create an array d of length 4 (same as string length) initialized with -1:

d = [-1, -1, -1, -1]

Now we check each replacement operation:

Operation 0 (k=0):

• Check if sources[0] = "a" appears at indices[0] = 0 in string "abcd"
• Yes! "abcd" starts with "a" at position 0
• Mark d[0] = 0 (indicating operation 0 should happen at position 0)
• d = [0, -1, -1, -1]

Operation 1 (k=1):

• Check if sources[1] = "cd" appears at indices[1] = 2 in string "abcd"
• Yes! Starting at position 2, we have "cd"
• Mark d[2] = 1 (indicating operation 1 should happen at position 2)
• d = [0, -1, 1, -1]

Phase 2: Build the Result String

Now we traverse the original string using our marking array:

ans = []
i = 0

Position i=0:

• Check d[0] = 0 (not -1, so a replacement exists)
• Append targets[0] = "eee" to result
• Jump forward by len(sources[0]) = len("a") = 1
• ans = ["eee"], i = 1

Position i=1:

• Check d[1] = -1 (no replacement)
• Append s[1] = "b" to result
• Move to next position
• ans = ["eee", "b"], i = 2

Position i=2:

• Check d[2] = 1 (not -1, so a replacement exists)
• Append targets[1] = "ffff" to result
• Jump forward by len(sources[1]) = len("cd") = 2
• ans = ["eee", "b", "ffff"], i = 4

Position i=4:

• We've reached the end (i >= 4)

Final Result: Join all parts: "".join(["eee", "b", "ffff"]) = "eeebffff"

The key insight is that by marking positions first, we ensure all replacements reference the original string positions. When we find "cd" at position 2, it's based on the original "abcd", not any intermediate result after replacing "a" with "eee".

Solution Implementation

Time and Space Complexity

Time Complexity: O(L) where L is the sum of the lengths of all strings (including s, all strings in sources, and all strings in targets).

The analysis breaks down as follows:

• The first loop iterates through all k replacements, where each iteration checks s.startswith(src, i). This operation takes O(len(src)) time for each source string. The total time for this loop is O(sum of lengths of all source strings).
• The second while loop traverses the string s once. At position i, if a replacement is found, we append the target string to ans (which takes O(1) amortized time for list append) and skip ahead by the length of the source string. If no replacement is found, we append a single character. Overall, this loop processes each character of s exactly once, contributing O(n) time.
• The "".join(ans) operation at the end takes O(length of final result) time, which is bounded by O(sum of lengths of all target strings + n).

Since we process the original string s and potentially all source and target strings, the total time complexity is O(n + sum of lengths of sources + sum of lengths of targets) = O(L).

Space Complexity: O(n) where n is the length of string s.

The space analysis:

• The array d uses O(n) space to store indices.
• The ans list stores the result, which in the worst case could be longer than n (if replacements make the string longer), but the auxiliary space used by d is exactly O(n).
• Other variables use O(1) space.

The dominant space usage is the d array of size n, giving us O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Processing Replacements in Sequential Order Instead of Simultaneously

A major pitfall is attempting to process replacements one by one in the order they appear in the arrays, which would cause earlier replacements to affect the indices of later ones.

Incorrect Approach:

# WRONG: This modifies the string after each replacement
for i, src, tgt in zip(indices, sources, targets):
    if s[i:i+len(src)] == src:
        s = s[:i] + tgt + s[i+len(src):]  # This changes indices!

Why it fails: After replacing "ab" with "eee" at index 0, the string length changes, making all subsequent indices incorrect.

Solution: Use the mapping array approach shown in the correct solution, which marks all valid replacements first based on the original string positions.

2. Not Handling Overlapping Replacement Attempts

While the problem guarantees no overlaps in valid replacements, you might incorrectly assume all attempted replacements will be valid and accidentally process overlapping regions.

Incorrect Approach:

# WRONG: Assuming all replacements are valid without checking
for k in range(len(indices)):
    result[indices[k]:indices[k]+len(sources[k])] = targets[k]

Solution: Always verify that sources[i] actually matches at indices[i] before marking it for replacement. The correct code uses s.startswith(source_string, start_index) to validate.

3. Incorrect Index Advancement After Replacement

When building the result string, failing to skip the correct number of characters after a replacement is a common error.

Incorrect Approach:

# WRONG: Always advancing by 1
while i < n:
    if ~replacement_map[i]:
        result.append(targets[replacement_map[i]])
        i += 1  # Should skip len(sources[...]) characters!
    else:
        result.append(s[i])
        i += 1

Why it fails: This would include characters from the original source string that should have been replaced.

Solution: After performing a replacement, advance the position by len(sources[operation_index]) to skip over the entire replaced substring.

4. Misunderstanding the Bitwise NOT Operator

Using if replacement_map[i]: instead of if ~replacement_map[i]: would fail because 0 is a valid replacement index.

Incorrect Approach:

# WRONG: This treats index 0 as False
if replacement_map[i]:  # Fails when replacement_map[i] == 0
    # perform replacement

Solution: Use ~replacement_map[i] which only evaluates to False when the value is -1, or alternatively use explicit comparison: if replacement_map[i] != -1: