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 string S and a list of replacement operations. Each operation [index, source, target] means: if S starts with source at index, replace it with target. Operations occur simultaneously.

Key Challenge: Indices refer to the original string S. If you modify S in-place from left to right, subsequent indices will shift and become invalid.

Strategy:

1. Map Operations: Create a lookup table (array or map) where table[index] stores the valid replacement operation.
2. Linear Scan: Build the result string by iterating S from 0 to N-1. If table[i] exists, append target and skip source.length. Else, append S[i].

---

2. Interactive Analysis

Watch how the result string is built.

Original (S):

Result:

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

---

3. Implementation

Java

Go

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 (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();
}

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()
}

---

4. Complexity Analysis

Strategy	Time	Space	Notes
Linear Scan	O(N + M)	O(N)	N=String Len, M=Ops Count.