Find And Replace in String

Medium
1210.

Find And Replace in String

Find And Replace in String is a medium coding problem on arrays, strings and hash table, asked in Amazon, Google and Microsoft interviews.

You are given a string s and k replacement operations described by three parallel arrays indices, sources and targets.

Operation i checks whether sources[i] occurs in the original s starting exactly at index indices[i]. If it does, that occurrence is replaced by targets[i]; if it does not, the operation does nothing.

All operations are applied simultaneously — every check looks at the original string, and replacing text never shifts the indices other operations refer to. The inputs guarantee that no two operations that do match overlap. The operations are not given in any particular order. Return the resulting string.

Example 1

Input
s = "codekairo", indices = [0,4], sources = ["code","kai"], targets = ["bug","hunt"]
Output
bughuntro

Example 2

Input
s = "pairroom", indices = [4,0], sources = ["room","pear"], targets = ["mode","duel"]
Output
pairmode
Explanation
`pear` does not occur at index 0, so only the first operation applies.

Example 3

Input
s = "aaa", indices = [2,0], sources = ["a","aa"], targets = ["z","b"]
Output
bz

Constraints

  • 1 <= s.length <= 1000
  • k == indices.length == sources.length == targets.length
  • 1 <= k <= 100
  • 0 <= indices[i] < s.length
  • 1 <= sources[i].length, targets[i].length <= 50
  • s, sources[i] and targets[i] consist of lowercase English letters
  • The values of indices are distinct, and matching operations never overlap
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number[]} indices
 * @param {string[]} sources
 * @param {string[]} targets
 * @return {string}
 */
var findReplaceString = function(s, indices, sources, targets) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find And Replace in String — Solution in Python, Java & C++

Find And Replace in String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find And Replace in String is a medium coding problem on arrays, strings and hash table, asked in Amazon, Google and Microsoft interviews.

Problem statement

You are given a string s and k replacement operations described by three parallel arrays indices, sources and targets.

Operation i checks whether sources[i] occurs in the original s starting exactly at index indices[i]. If it does, that occurrence is replaced by targets[i]; if it does not, the operation does nothing.

All operations are applied simultaneously — every check looks at the original string, and replacing text never shifts the indices other operations refer to. The inputs guarantee that no two operations that do match overlap. The operations are not given in any particular order. Return the resulting string.

Example 1

Input: s = "codekairo", indices = [0,4], sources = ["code","kai"], targets = ["bug","hunt"]
Output: bughuntro

Example 2

Input: s = "pairroom", indices = [4,0], sources = ["room","pear"], targets = ["mode","duel"]
Output: pairmode
Explanation: `pear` does not occur at index 0, so only the first operation applies.

Example 3

Input: s = "aaa", indices = [2,0], sources = ["a","aa"], targets = ["z","b"]
Output: bz

Constraints

  • 1 <= s.length <= 1000
  • k == indices.length == sources.length == targets.length
  • 1 <= k <= 100
  • 0 <= indices[i] < s.length
  • 1 <= sources[i].length, targets[i].length <= 50
  • s, sources[i] and targets[i] consist of lowercase English letters
  • The values of indices are distinct, and matching operations never overlap

Hints for Find And Replace in String

  1. Hint 1

    Decide first which operations match, using the original string only.

  2. Hint 2

    Record, for each starting index, which operation (if any) matched there.

  3. Hint 3

    Then build the answer left to right: at a recorded index emit the target and jump past the source; otherwise copy one character.

How to solve Find And Replace in String

Because every check reads the original string and matching ranges never overlap, the matches can be found first and the output built in a single left-to-right pass.

Approach

  1. Create match, an array of length n filled with −1.
  2. For each operation i, if s has sources[i] at position indices[i], set match[indices[i]] = i.
  3. Scan p from 0: if match[p] = j ≥ 0, append targets[j] and advance p by sources[j].length; otherwise append s[p] and advance by one.

Why it works

Recording matches against the untouched string implements the simultaneous semantics, and a position-indexed table removes any dependence on the order the operations were given in. Since matched ranges do not overlap, jumping over a replaced range never skips the start of another match.

Complexity

  • Time — O(n + Σ|sources[i]| + Σ|targets[i]|)
  • Space — O(n)

Pitfalls

  • Applying operations one by one on the changing string shifts later indices.
  • The operations are unsorted; processing them in input order without a table breaks.
  • A source may run past the end of s — that is simply a non-match, not an error.

Reference solution

Python

from typing import List

def findReplaceString(s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
    match = {}
    for i, idx in enumerate(indices):
        if s.startswith(sources[i], idx):
            match[idx] = i
    out = []
    p = 0
    while p < len(s):
        if p in match:
            j = match[p]
            out.append(targets[j])
            p += len(sources[j])
        else:
            out.append(s[p])
            p += 1
    return "".join(out)

Java

public static String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
    int n = s.length();
    int[] match = new int[n];
    Arrays.fill(match, -1);
    for (int k = 0; k < indices.length; k++) {
        if (s.startsWith(sources[k], indices[k])) match[indices[k]] = k;
    }
    StringBuilder sb = new StringBuilder();
    for (int p = 0; p < n; ) {
        int j = match[p];
        if (j >= 0) {
            sb.append(targets[j]);
            p += sources[j].length();
        } else {
            sb.append(s.charAt(p));
            p++;
        }
    }
    return sb.toString();
}

C++

string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
    int n = (int)s.size();
    vector<int> match(n, -1);
    for (size_t k = 0; k < indices.size(); k++) {
        if (s.compare(indices[k], sources[k].size(), sources[k]) == 0) match[indices[k]] = (int)k;
    }
    string out;
    for (int p = 0; p < n; ) {
        int j = match[p];
        if (j >= 0) {
            out += targets[j];
            p += (int)sources[j].size();
        } else {
            out.push_back(s[p]);
            p++;
        }
    }
    return out;
}

JavaScript

var findReplaceString = function(s, indices, sources, targets) {
    var n = s.length;
    var match = [];
    for (var i = 0; i < n; i++) match.push(-1);
    for (var k = 0; k < indices.length; k++) {
        var idx = indices[k];
        if (s.substring(idx, idx + sources[k].length) === sources[k]) match[idx] = k;
    }
    var out = [];
    for (var p = 0; p < n; ) {
        var j = match[p];
        if (j >= 0) {
            out.push(targets[j]);
            p += sources[j].length;
        } else {
            out.push(s[p]);
            p++;
        }
    }
    return out.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings