Find and Replace in String

[!NOTE] This module explores the core principles of Find and Replace in String, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

Problem: You are given a zero-indexed string S and a list of replacement operations. Each operation consists of an index, a source string, and a target string. If S starts with the source string at the given index, you must replace that occurrence with the target string. All replacement operations occur simultaneously. If multiple operations overlap, they will not be executed.

Constraints:

• 1 <= S.length <= 1000
• k == indices.length == sources.length == targets.length
• 1 <= k <= 100
• 0 <= indices[i] < S.length
• 1 <= sources[i].length, targets[i].length <= 50
• S, sources[i], and targets[i] consist of lowercase English letters.

Examples:

Input: S = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Output: "eeebffff"
Explanation:
"a" starts at index 0 in S, so it's replaced by "eee".
"cd" starts at index 2 in S, so it's replaced by "ffff".

Input: S = "abcd", indices = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation:
"ab" starts at index 0 in S, so it's replaced by "eee".
"ec" does not start at index 2 in S, so we do nothing.

Edge Cases & Clarifying Questions:

• What if the source strings overlap? The problem guarantees that there will be no overlap for successful replacements.
• What if indices are not sorted? The operations are given in no particular order, so we shouldn’t assume they are sorted by index.
• What if a replacement index is out of bounds or source extends beyond S? The replacement operation should be ignored.

2. Intuition (The “Genesis”)

Brute Force Approach

The naive approach is to perform each replacement operation one by one on the string S. We iterate through the given operations, check if the source string matches S at the specified index, and if it does, we create a new string with the replacement applied.

However, this introduces a critical issue: index shifting. Because the replacements are supposed to occur simultaneously, replacing a substring with another of a different length alters the indices of the original string. If we perform the operations sequentially, the original indices provided for subsequent operations will no longer point to the correct locations in the modified string. To fix this in the brute force approach, we would need to manually keep track of the index offsets caused by previous replacements and apply them to future operations, which is highly error-prone and complex, especially since the operations are not sorted.

Optimized Approach: Linear Scan with Lookup Table

To solve the index shifting problem, we need a method that evaluates operations based on their original positions. We can achieve this by explicitly naming the pattern: the Parallel Array / Lookup Table approach.

Instead of modifying the string in place, we can construct the result by scanning the original string S from left to right. Since we process the string sequentially, we need to know if an operation applies at the current index i. We can pre-process all the replacement operations into a lookup table (or an array match of size N), where match[i] stores the index of the operation that successfully matches S starting at index i.

1. Validation Step: Iterate through all provided operations. For each operation k at indices[k], check if the substring in S starting at indices[k] matches sources[k]. If it does, we record match[indices[k]] = k.
2. Construction Step: Iterate through S using a pointer i. If match[i] has a valid operation k, append targets[k] to the result string, and advance i by the length of sources[k]. If no valid operation exists at i, simply append S[i] to the result and increment i by 1.

Common Pitfalls

• Assuming operations are sorted: The input indices array is not necessarily sorted. Processing them in order without a lookup table can lead to incorrect offset calculations.
• Out of bounds errors: When checking if S matches sources[k], you must ensure that indices[k] + sources[k].length does not exceed the bounds of S.
• String concatenation overhead: In languages like Java or Go, repeatedly concatenating strings using + in a loop creates many intermediate string objects, leading to O(N²) time complexity. Always use StringBuilder or strings.Builder.

3. Interactive Analysis

Watch how the result string is built.

Original (S):

Result:

Ready. Operations: (0, "ab", "eee"), (4, "ec", "ffff")

---

4. Solutions

Java

public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
  int n = s.length();
  int[] match = new int[n];
  Arrays.fill(match, -1);

  // 1. Pre-process Operations
  for (int i = 0; i < indices.length; i++) {
    int idx = indices[i];
    // Valid replacement check
    if (idx + sources[i].length() <= n && s.substring(idx, idx + sources[i].length()).equals(sources[i])) {
      match[idx] = i; // Store index of the operation
    }
  }

  // 2. Build Result
  StringBuilder sb = new StringBuilder();
  int i = 0;
  while (i < n) {
    if (match[i] != -1) {
      sb.append(targets[match[i]]);
      i += sources[match[i]].length();
    } else {
      sb.append(s.charAt(i));
      i++;
    }
  }
  return sb.toString();
}

Go

func findReplaceString(s string, indices []int, sources []string, targets []string) string {
  n := len(s)
  match := make([]int, n)
  for i := range match { match[i] = -1 }

  // 1. Pre-process
  for k, idx := range indices {
    src := sources[k]
    if idx+len(src) <= n && s[idx:idx+len(src)] == src {
      match[idx] = k
    }
  }

  // 2. Build
  var sb strings.Builder
  i := 0
  for i < n {
    if match[i] != -1 {
      sb.WriteString(targets[match[i]])
      i += len(sources[match[i]])
    } else {
      sb.WriteByte(s[i])
      i++
    }
  }
  return sb.String()
}

---

5. Complexity Analysis

Strategy	Time	Space	Notes
Brute Force (Sequential)	O(M × N)	O(M × N)	Needs to track offset changes, creates intermediate strings.
Linear Scan (Lookup Table)	O(N + M × L)	O(N)	N = Length of S, M = Number of operations, L = Max length of source string.