Find And Replace in String

Find And Replace in String trips people up because of one word: offsets. You replace parts of a string at given spots. But every replacement changes the length. So the spots shift. The interviewer wants to see if you handle that shifting cleanly instead of getting lost in moving positions.

🎯 The Problem

You run replacement jobs on a string, but only where the job truly matches.

• Each job has a position, a source word to look for, and a target word to swap in.
• A job fires only if the source word really sits at that position.
• If it matches, swap in the target. If not, leave that spot alone.
• All positions point at the original string, not the changed one. So check every match against the original.

For "abcd": one job is at position 0, look for "a", replace with "eee". Another is at position 2, look for "cd", replace with "ffff". Both match. The result is "eeebffff".

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

Explanation: at 0 "a" -> "eee", letter b stays, at 2 "cd" -> "ffff".

Here is how each job maps onto the original string.

🐢 Approach 1: Replace Left to Right and Shift (Brute Force)

The idea in one line: edit the string job by job and track how much each edit moves the later positions.

The idea:

• Do the jobs one by one from left to right.
• Cut out the source. Paste in the target.

How it works:

• Each replacement changes the length, so later positions move.
• That shift is called an offset. It is the move in positions caused by an earlier change.
• After adding "eee" for "a", the next job’s position is off by two. You add that shift yourself.

Why it is weak:

• The offset math is easy to get wrong.
• One mistake and the whole answer is off.

Here is the left-to-right replacement code:

def find_replace_string(s, indices, sources, targets):
    shift = 0
    jobs = sorted(zip(indices, sources, targets))

    for index, source, target in jobs:
        real_index = index + shift
        if s.startswith(source, real_index):
            s = s[:real_index] + target + s[real_index + len(source):]
            shift += len(target) - len(source)

    return s

⚡ Approach 2: Sort Jobs and Build Once (Best)

The idea in one line: never edit the original, build a fresh string while sweeping left to right.

The idea:

• Do not touch the original string.
• Build a brand new string from left to right.
• First sort the jobs by position, from smallest to largest, so we can sweep once.

How it works:

• Walk a pointer along the original string.
• If a job starts here and its source matches the original, add the target and jump the pointer past the source.
• If no job starts here, copy the current character and move the pointer by one.

Why it is fast:

• We always check matches against the original, so positions never shift.
• There is no offset math at all.

Here is the build sweep on the example.

Steps to Solve

1. Pair each job’s position with its source and target. Sort these jobs by position.
2. Start a pointer at the beginning of the original string and an empty result.
3. Walk the pointer along the string.
4. If a job starts at the pointer and its source matches the original string there, add the target to the result and move the pointer past the source.
5. If no job matches here, copy the current character to the result and move the pointer by one.
6. When the pointer reaches the end, return the result.

#include <stdio.h>
#include <string.h>

int main(void) {
    char s[] = "abcd";
    int indices[] = {0, 2};
    const char *sources[] = {"a", "cd"};
    const char *targets[] = {"eee", "ffff"};
    int jobs = 2;
    int n = strlen(s);

    char out[100];
    int pos = 0;
    int i = 0;
    while (i < n) {
        int matched = 0;
        for (int j = 0; j < jobs; j++) {       // find a job starting here
            if (indices[j] == i &&
                strncmp(s + i, sources[j], strlen(sources[j])) == 0) {
                strcat(out + pos, targets[j]);  // add the target
                pos += strlen(targets[j]);
                i += strlen(sources[j]);        // jump past the source
                matched = 1;
                break;
            }
        }
        if (!matched) {                         // no job, copy one char
            out[pos++] = s[i];
            i++;
        }
    }
    out[pos] = '\0';
    printf("%s\n", out);
    return 0;
}

eeebffff

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

string findReplace(string s, vector<int> indices,
                   vector<string> sources, vector<string> targets) {
    int n = indices.size();
    vector<int> order(n);
    for (int i = 0; i < n; i++) order[i] = i;
    sort(order.begin(), order.end(), [&](int a, int b) {  // sort by index
        return indices[a] < indices[b];
    });
    string result = "";
    int i = 0, k = 0;
    while (i < (int)s.size()) {
        if (k < n && indices[order[k]] == i &&
            s.compare(i, sources[order[k]].size(), sources[order[k]]) == 0) {
            result += targets[order[k]];        // add the target
            i += sources[order[k]].size();      // jump past the source
            k++;
        } else {
            if (k < n && indices[order[k]] == i) k++;  // job that did not match
            result += s[i];                     // copy one char
            i++;
        }
    }
    return result;
}

int main() {
    cout << findReplace("abcd", {0, 2}, {"a", "cd"}, {"eee", "ffff"}) << endl;
    return 0;
}

eeebffff

import java.util.HashMap;
import java.util.Map;

public class FindReplaceInString {
    public static String findReplace(String s, int[] indices,
                                     String[] sources, String[] targets) {
        Map<Integer, Integer> jobAt = new HashMap<>();   // index -> job number
        for (int j = 0; j < indices.length; j++) {
            jobAt.put(indices[j], j);
        }
        StringBuilder result = new StringBuilder();
        int i = 0;
        while (i < s.length()) {
            if (jobAt.containsKey(i)) {
                int j = jobAt.get(i);
                if (s.startsWith(sources[j], i)) {   // source matches here
                    result.append(targets[j]);       // add the target
                    i += sources[j].length();        // jump past the source
                    continue;
                }
            }
            result.append(s.charAt(i));              // copy one char
            i++;
        }
        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(findReplace("abcd", new int[]{0, 2},
            new String[]{"a", "cd"}, new String[]{"eee", "ffff"}));
    }
}

eeebffff

def find_replace(s, indices, sources, targets):
    job_at = {}                       # index -> job number
    for j in range(len(indices)):
        job_at[indices[j]] = j
    result = []
    i = 0
    while i < len(s):
        if i in job_at:                       # a job starts at this index
            j = job_at[i]
            if s.startswith(sources[j], i):   # source matches the original here
                result.append(targets[j])     # add the target word
                i += len(sources[j])          # jump past the matched source
                continue
        result.append(s[i])                   # no match, copy one character
        i += 1
    return "".join(result)


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

eeebffff

function findReplace(s, indices, sources, targets) {
  const jobAt = new Map(); // index -> job number
  for (let j = 0; j < indices.length; j++) {
    jobAt.set(indices[j], j);
  }
  let result = "";
  let i = 0;
  while (i < s.length) {
    if (jobAt.has(i)) {                  // a job starts here
      const j = jobAt.get(i);
      if (s.startsWith(sources[j], i)) { // source matches the original
        result += targets[j];            // add the target
        i += sources[j].length;          // jump past the source
        continue;
      }
    }
    result += s[i];                      // no match, copy one char
    i++;
  }
  return result;
}

console.log(findReplace("abcd", [0, 2], ["a", "cd"], ["eee", "ffff"]));

eeebffff

Let us walk through the Python version line by line, because it shows how we dodge the offset problem.

job_at = {} is a map from an index to its job number. We build it so that when our pointer reaches some index, we can ask in one step “is there a job here?”. The lookup is instant.

for j in range(len(indices)): job_at[indices[j]] = j fills that map. For each job we store its index pointing to its job number. So index 0 points to job 0, and index 2 points to job 1.

result = [] is where we build the new string. We use a list and join at the end because that is faster than adding to a string over and over.

while i < len(s): sweeps the pointer i along the original string. Notice we walk the original, never a changed copy. That is the whole reason the offsets never bite us.

if i in job_at: checks whether a job starts at the current index. If yes, we grab its job number with j = job_at[i].

if s.startswith(sources[j], i): checks the source actually sits at index i in the original. The startswith with a start position is the clean way to test a match at a spot. A job only fires if its source really matches.

result.append(targets[j]) adds the target word in place of the source. Then i += len(sources[j]) jumps the pointer past the whole source. So we never re-read the letters we just replaced. The continue sends us back to the top of the loop.

result.append(s[i]); i += 1 is the no-match path. If no job starts here, or the source did not match, we copy the single character and move on by one.

return "".join(result) glues all the kept and replaced pieces into the final string.

⏱️ Time and Space Complexity

The naive shift approach edits the string again and again, and tracking offsets is error-prone and can be slow. The sweep approach walks the string once and does a quick match check at each job index. Sorting the jobs costs O(k log k), where k is the number of jobs. The sweep itself is O(n) for the string length. The new string takes O(n) space. So this is fast and, more importantly, it never gets tangled in shifting positions, which keeps it correct.

🧩 Key Takeaways

• ✅ All job positions point at the original string, so always check matches there.
• ✅ Build a new string instead of editing the old one, so positions never shift.
• ✅ A job only fires if its source word truly sits at that index.
• ✅ When a job fires, jump the pointer past the whole source word.
• ✅ This avoids all the offset math that makes the naive approach buggy.

🚀 What’s Next?

• Minimum Remove to Make Valid Parentheses
• Custom Sort String