Find And Replace in String

Find And Replace in String

What is this problem about?

In the Find And Replace in String coding problem, you are given a base string s and several replacement operations. Each operation consists of an index, a source string, and a target string. An operation is only performed if the substring of s starting at index exactly matches source. Crucially, all replacements must be determined based on the original string, and they must not interfere with each other.

Why is this asked in interviews?

Google uses this to test your ability to handle overlapping string modifications and sorting. Since replacing a string with a longer or shorter target changes the indices of subsequent characters, doing it "on the fly" is prone to errors. It evaluation your proficiency with Hash Tables and the String interview pattern of building a result string incrementally while mapping original positions to new values.

Algorithmic pattern used

The problem is best solved by Preprocessing and Building.

1. Identify which operations are valid by checking s.startsWith(source, index).
2. Create a way to quickly look up an operation by its original start index (e.g., an array or map).
3. Iterate through the original string s using a pointer i = 0.
4. If index i has a valid replacement:
   • Append the target string to your result.
   • Increment i by the length of the source string.
5. If no replacement at i:
   • Append s[i] to the result.
   • Increment i by 1.

Example explanation

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

1. Check index 0: "a" matches "abcd" at 0. Valid.
2. Check index 2: "cd" matches "abcd" at 2. Valid.
3. Build:
   • At i=0: Replace "a" with "eee". Result: "eee". $i$ moves to 1.
   • At i=1: No replacement. Result: "eeeb". $i$ moves to 2.
   • At i=2: Replace "cd" with "ffff". Result: "eeebffff". $i$ moves to 4.
4. Final result: "eeebffff".

Common mistakes candidates make

• Modifying the string directly: This shifts the indices, making the indices array in the input invalid for subsequent operations.
• Not sorting operations: If you process operations by index, you can build the string linearly. If you don't, you might skip parts of the string.
• Handling overlapping sources: The problem usually guarantees no overlaps, but failing to check for the source match before replacing is a common logic error.

Interview preparation tip

When performing multiple modifications on a string, don't try to edit the string in place. Instead, treat the original string as a read-only template and use a StringBuilder or a list of characters to construct the final output. This avoids complex index arithmetic.