Apply k replacement operations on string s: if s[indices[i]..] starts with sources[i], replace with targets[i].
Input: s="abcd", indices=[0,2], sources=["a","cd"], targets=["eee","ffff"] → Output: "eeebffff"
Input: s="abcd", indices=[0,2], sources=["ab","ec"], targets=["eee","ffff"] → Output: "eeecd"
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
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)