LeetCode 833 - Find And Replace in String

LeetCode Problem 833

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Sorting

Solution

Problem Understanding

The problem gives us a string s and three parallel arrays:

• indices[i] tells us where a replacement might happen
• sources[i] is the substring we expect to find at that index
• targets[i] is the string we should replace it with if the match is valid

For each operation, we must check whether sources[i] actually appears in the original string s starting at indices[i]. If it does, we replace that substring with targets[i]. If it does not, we leave the string unchanged for that operation.

The important detail is that all replacements happen simultaneously. This means replacements cannot affect the positions of later replacements. Every check must be performed against the original string, not a partially modified one.

For example:

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

At index 0, the substring "a" matches, so we replace it with "eee".

At index 2, the substring "cd" matches, so we replace it with "ffff".

The final result becomes "eeebffff".

The constraints are relatively small:

• s.length <= 1000
• k <= 100
• sources[i].length <= 50

These limits mean we do not need highly advanced algorithms like suffix arrays or rolling hashes. A straightforward string scanning solution is efficient enough.

The problem also guarantees that valid replacement regions never overlap. This is extremely important because it means we never need to resolve conflicts between multiple replacements touching the same characters.

Several edge cases are important:

• A source string may not match at its index.
• Replacements may appear in arbitrary order.
• Some replacements may occur near the end of the string.
• Target strings may be longer or shorter than source strings.
• Multiple valid replacements may exist, but they are guaranteed not to overlap.

A naive implementation that modifies the string immediately while iterating could break indexing for later replacements, which is why the "simultaneous" requirement matters.

Approaches

Brute Force Approach

The most direct approach is to process replacements one by one directly on the string.

For each operation:

1. Check whether the source matches at the specified index.
2. If it matches, modify the string immediately.

However, this creates a problem. Once the string changes length, all later indices may become invalid because the original indexing no longer matches the updated string.

One possible workaround is to sort operations in descending index order so that modifications on the right do not affect positions on the left. This works, but repeated string slicing and concatenation still creates unnecessary overhead.

Although the constraints are small enough that this solution would pass, it is not the cleanest interpretation of the simultaneous replacement requirement.

Optimal Approach

The key insight is that every replacement decision depends only on the original string.

Instead of repeatedly modifying the string, we can:

1. Precompute which indices have valid replacements.
2. Scan the original string from left to right.
3. Build the answer incrementally.

At each position:

• If a valid replacement starts there, append the target string and skip the source length.
• Otherwise append the current character normally.

This approach naturally preserves simultaneous behavior because all checks are made against the original string before construction begins.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k * n)	O(n)	Repeated string rebuilding after each replacement
Optimal	O(n + total source length)	O(k + n)	Single left to right scan with preprocessed replacements

Algorithm Walkthrough

1. Create a hash map that stores valid replacements.

The key will be the starting index of a replacement. The value will contain:

• the source string
• the target string

We only store replacements whose source actually matches the original string at that index. 2. Iterate through all replacement operations.

For each operation:

• Let start = indices[i]
• Let source = sources[i]
• Check whether:

s[start:start + len(source)] == source

If the substring matches, store this replacement in the hash map. 3. Initialize an empty result list.

We use a list because repeatedly concatenating Python strings is inefficient. 4. Start scanning the string from left to right using pointer i. 5. At each position, check whether a valid replacement starts at i.

If i exists in the replacement map:

• Append the corresponding target string
• Advance i by the length of the source string

Otherwise:

• Append s[i]
• Advance i by 1

6. Continue until the entire string has been processed.
7. Join the result list into the final string and return it.

Why it works

The algorithm works because every replacement decision is determined before any modifications occur. Since all checks are performed against the original string, the simultaneous replacement requirement is preserved.

During the left to right scan, each character position is processed exactly once. Because replacements are guaranteed not to overlap, skipping over replaced substrings is always safe and never misses another valid replacement.

Python Solution

from typing import List

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

        replacements = {}

        # Store only valid replacements
        for index, source, target in zip(indices, sources, targets):
            if s[index:index + len(source)] == source:
                replacements[index] = (source, target)

        result = []
        i = 0

        while i < len(s):
            if i in replacements:
                source, target = replacements[i]

                result.append(target)

                # Skip the matched source substring
                i += len(source)
            else:
                result.append(s[i])
                i += 1

        return "".join(result)

The implementation begins by preprocessing all valid replacements. We iterate through the parallel arrays simultaneously using zip.

For each replacement operation, we verify whether the source string truly exists at the specified index in the original string. If it does, we store the replacement in the replacements dictionary.

The dictionary allows constant time lookup while scanning the string later.

Next, we build the final result using a left to right traversal. The pointer i represents the current position in the original string.

If a replacement begins at i, we append the target string and skip the entire source substring length. Otherwise, we copy the current character directly into the result.

Finally, we join the collected pieces into the final output string.

Go Solution

package main

import "strings"

func findReplaceString(s string, indices []int, sources []string, targets []string) string {
	type Replacement struct {
		source string
		target string
	}

	replacements := make(map[int]Replacement)

	// Store only valid replacements
	for i := 0; i < len(indices); i++ {
		index := indices[i]
		source := sources[i]

		if s[index:index+len(source)] == source {
			replacements[index] = Replacement{
				source: source,
				target: targets[i],
			}
		}
	}

	var builder strings.Builder

	for i := 0; i < len(s); {
		if replacement, exists := replacements[i]; exists {
			builder.WriteString(replacement.target)
			i += len(replacement.source)
		} else {
			builder.WriteByte(s[i])
			i++
		}
	}

	return builder.String()
}

The Go implementation follows the same algorithmic structure as the Python version.

Instead of using Python tuples, Go uses a small Replacement struct to store the source and target strings.

The result string is constructed using strings.Builder, which is the idiomatic and efficient way to build strings incrementally in Go.

Since the problem constraints are small, there are no integer overflow concerns. Go string slicing also works efficiently for substring comparisons.

Worked Examples

Example 1

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

Step 1, Validate replacements

Index	Source	Target	Match?
0	"a"	"eee"	Yes
2	"cd"	"ffff"	Yes

Replacement map:

{
    0: ("a", "eee"),
    2: ("cd", "ffff")
}

Step 2, Scan the string

i	Current Action	Result
0	Replace "a" with "eee"	"eee"
1	Skipped because source length was 1	"eee"
2	Replace "cd" with "ffff"	"eeebffff"

Final answer:

"eeebffff"

Example 2

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

Step 1, Validate replacements

Index	Source	Target	Match?
0	"ab"	"eee"	Yes
2	"ec"	"ffff"	No

Replacement map:

{
    0: ("ab", "eee")
}

Step 2, Scan the string

i	Current Action	Result
0	Replace "ab" with "eee"	"eee"
2	Append "c"	"eeec"
3	Append "d"	"eeecd"

Final answer:

"eeecd"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + total source length)	One preprocessing pass and one linear scan
Space	O(n + k)	Replacement map and output buffer

The preprocessing step checks each source string once. Since each source length is at most 50, the total substring checking cost is small.

The main traversal processes each character of the string exactly once. Every replacement skip is still part of the same linear scan, so the total runtime remains linear in practice.

The space complexity comes from:

• The replacement hash map
• The output buffer used to build the final string

Test Cases

from typing import List

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

        replacements = {}

        for index, source, target in zip(indices, sources, targets):
            if s[index:index + len(source)] == source:
                replacements[index] = (source, target)

        result = []
        i = 0

        while i < len(s):
            if i in replacements:
                source, target = replacements[i]
                result.append(target)
                i += len(source)
            else:
                result.append(s[i])
                i += 1

        return "".join(result)

sol = Solution()

# Provided example 1
assert sol.findReplaceString(
    "abcd",
    [0, 2],
    ["a", "cd"],
    ["eee", "ffff"]
) == "eeebffff"

# Provided example 2
assert sol.findReplaceString(
    "abcd",
    [0, 2],
    ["ab", "ec"],
    ["eee", "ffff"]
) == "eeecd"

# No replacements match
assert sol.findReplaceString(
    "abcd",
    [1],
    ["zz"],
    ["yyy"]
) == "abcd"

# Single character replacement
assert sol.findReplaceString(
    "abc",
    [1],
    ["b"],
    ["x"]
) == "axc"

# Replacement with longer target
assert sol.findReplaceString(
    "abc",
    [0],
    ["ab"],
    ["zzzzz"]
) == "zzzzzc"

# Replacement with shorter target
assert sol.findReplaceString(
    "abcdef",
    [2],
    ["cd"],
    ["x"]
) == "abxef"

# Multiple non-overlapping replacements
assert sol.findReplaceString(
    "abcdefgh",
    [0, 2, 6],
    ["ab", "cd", "gh"],
    ["11", "22", "33"]
) == "1122ef33"

# Replacements given in unsorted order
assert sol.findReplaceString(
    "abcd",
    [2, 0],
    ["cd", "ab"],
    ["XX", "YY"]
) == "YYXX"

# Replacement at end of string
assert sol.findReplaceString(
    "abcdef",
    [4],
    ["ef"],
    ["ZZ"]
) == "abcdZZ"

# Entire string replacement
assert sol.findReplaceString(
    "hello",
    [0],
    ["hello"],
    ["world"]
) == "world"

Test	Why
Example 1	Verifies multiple successful replacements
Example 2	Verifies failed replacement handling
No replacements match	Ensures original string remains unchanged
Single character replacement	Tests smallest valid replacement
Longer target	Confirms output length can increase
Shorter target	Confirms output length can decrease
Multiple non-overlapping replacements	Tests simultaneous behavior
Unsorted replacement indices	Ensures ordering does not matter
Replacement at end	Verifies boundary indexing
Entire string replacement	Tests maximum substring coverage

Edge Cases

Replacement source does not match

One common source of bugs is assuming every replacement operation is valid. The problem explicitly states that replacements should only happen if the source string exactly matches the substring at the given index.

For example:

s = "abcd"
index = 1
source = "zz"

Since "zz" does not appear starting at index 1, the replacement must be ignored.

The implementation handles this safely during preprocessing by checking:

s[index:index + len(source)] == source

Only valid replacements are stored.

Replacement indices are not sorted

The input arrays are not guaranteed to be sorted by index.

A naive implementation that processes replacements sequentially while modifying the string could produce incorrect results if replacements appear out of order.

The current solution avoids this entirely by:

1. Validating replacements independently
2. Using a dictionary keyed by index
3. Scanning the original string left to right

Because of this structure, the input order does not matter.

Target strings have different lengths

Another common issue is handling replacements where the target string length differs from the source length.

For example:

source = "ab"
target = "xyzxyz"

or

source = "abcdef"
target = "x"

If a solution modifies the string directly while iterating, index shifts can easily break later replacements.

This implementation avoids all indexing problems because it never edits the original string in place. Instead, it constructs a brand new result string incrementally.