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.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table, Sorting
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 1000k == indices.length == sources.length == targets.length1 <= k <= 1000 <= indices[i] < s.length1 <= sources[i].length, targets[i].length <= 50s, sources[i] and targets[i] consist of lowercase English lettersThe values of indices are distinct, and matching operations never overlap
Hints for Find And Replace in String
Hint 1
Decide first which operations match, using the original string only.
Hint 2
Record, for each starting index, which operation (if any) matched there.
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
- Create
match, an array of lengthnfilled with −1. - For each operation
i, ifshassources[i]at positionindices[i], setmatch[indices[i]] = i. - Scan
pfrom 0: ifmatch[p] = j ≥ 0, appendtargets[j]and advancepbysources[j].length; otherwise appends[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.