Find And Replace in String

medium string sorting simulation

Problem

Given a string s and arrays of indices, sources, and targets, replace each source[i] at indices[i] with target[i] if it matches. All replacements happen in parallel based on the original string.

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

Output"eeebffff"

Both substrings match, so both replacements apply.

input (fixed example)

def findReplaceString(s, indices, sources, targets):
    ops = sorted(zip(indices, sources, targets), reverse=True)
    s = list(s)
    out = "".join(s)
    for i, src, tgt in ops:
        if out[i:i + len(src)] == src:
            out = out[:i] + tgt + out[i + len(src):]
    return out

function findReplaceString(s, indices, sources, targets) {
  const ops = indices.map((idx, k) => [idx, sources[k], targets[k]])
                     .sort((a, b) => b[0] - a[0]);
  let out = s;
  for (const [i, src, tgt] of ops) {
    if (out.substr(i, src.length) === src) {
      out = out.slice(0, i) + tgt + out.slice(i + src.length);
    }
  }
  return out;
}

import java.util.*;
class Solution {
  public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
    Integer[] order = new Integer[indices.length];
    for (int k = 0; k < order.length; k++) order[k] = k;
    Arrays.sort(order, (a, b) -> indices[b] - indices[a]);
    StringBuilder sb = new StringBuilder(s);
    for (int k : order) {
      int i = indices[k]; String src = sources[k];
      if (i + src.length() <= sb.length() && sb.substring(i, i + src.length()).equals(src))
        sb.replace(i, i + src.length(), targets[k]);
    }
    return sb.toString();
  }
}

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        vector<int> order(indices.size());
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b){ return indices[a] > indices[b]; });
        for (int k : order) {
            int i = indices[k]; const string &src = sources[k];
            if (i + (int)src.size() <= (int)s.size() && s.compare(i, src.size(), src) == 0)
                s.replace(i, src.size(), targets[k]);
        }
        return s;
    }
};

Explanation

Every replacement is described by a starting index, a source substring to match, and a target to swap in. The catch is that all replacements are based on the original string, but actually splicing one in shifts the positions of everything after it. The clever fix is to apply the operations from right to left.

We pair up each (index, source, target) and sort them by index in descending order. By editing the rightmost spot first, any earlier index we still need stays valid, because nothing to its left has moved yet.

For each operation we check that the slice out[i:i+len(src)] really equals src. Only on a match do we splice in tgt; otherwise we leave that spot alone.

Example: s = "abcd", replace "a" at 0 with "eee" and "cd" at 2 with "ffff". Going right-to-left, index 2 matches cd → "abffff", then index 0 matches a → "eeebffff".

The sorting step is the main cost, and then each operation does a quick match-and-splice, so the work is dominated by that sort.

Time: O((n + k) log k) Space: O(n)