Find And Replace in String

Share

Apply k replacement operations on string s: if s[indices[i]..] starts with sources[i], replace with targets[i].

Example 1
Input: s="abcd", indices=[0,2], sources=["a","cd"], targets=["eee","ffff"] → Output: "eeebffff"
Example 2
Input: s="abcd", indices=[0,2], sources=["ab","ec"], targets=["eee","ffff"] → Output: "eeecd"

Solution Approach

Sort operations by index descending, apply replacements from right to left to avoid index shifting.

  • Create list of (index, source, target) and sort by index descending
  • For each operation: check if s starts with source at index
  • If yes: replace that portion
  • Apply from right to left to preserve indices
  • Return result
Java
public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
    Integer[] order = new Integer[indices.length];
    for (int i = 0; i < order.length; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> indices[b] - indices[a]);
    StringBuilder sb = new StringBuilder(s);
    for (int i : order) {
        int idx = indices[i];
        String src = sources[i], tgt = targets[i];
        if (sb.indexOf(src, idx) == idx)
            sb.replace(idx, idx + src.length(), tgt);
    }
    return sb.toString();
}
  • Time Complexity: O(n log n + n*m)
  • Space Complexity: O(n)