Find And Replace in String - Video Solutions
Google Coding Interview Question | Leetcode 833 | Find And Replace in String
Find And Replace in String - Video Solution
Watch 6 video solutions for Find And Replace in String, a medium level problem involving Array, Hash Table, String. This walkthrough by WorkWithGoogler has 4,881 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.
To complete the ith replacement operation:
- Check if the substring
sources[i]occurs at indexindices[i]in the original strings. - If it does not occur, do nothing.
- Otherwise if it does occur, replace that substring with
targets[i].
For example, if s = "abcd", indices[i] = 0, sources[i] = "ab", and targets[i] = "eee", then the result of this replacement will be "eeecd".
All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.
- For example, a testcase with
s = "abc",indices = [0, 1], andsources = ["ab","bc"]will not be generated because the"ab"and"bc"replacements overlap.
Return the resulting string after performing all replacement operations on s.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"] Output: "eeebffff" Explanation: "a" occurs at index 0 in s, so we replace it with "eee". "cd" occurs at index 2 in s, so we replace it with "ffff".
Example 2:
Input: s = "abcd", indices = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"] Output: "eeecd" Explanation: "ab" occurs at index 0 in s, so we replace it with "eee". "ec" does not occur at index 2 in s, so we do nothing.
Constraints:
1 <= s.length <= 1000k == indices.length == sources.length == targets.length1 <= k <= 1000 <= indexes[i] < s.length1 <= sources[i].length, targets[i].length <= 50sconsists of only lowercase English letters.sources[i]andtargets[i]consist of only lowercase English letters.
Approach Overview
Problem Overview: You receive a base string s and three arrays: indices, sources, and targets. For each index i, replace the substring starting at indices[i] with targets[i] only if the substring exactly matches sources[i]. All replacements must behave as if they occur simultaneously.
Approach 1: Simultaneous Replacement using Sorting (O(n + k log k) time, O(n) space)
This approach sorts replacement operations by their starting index so you can scan the string from left to right while applying valid replacements. Pair each index with its corresponding source and target, then sort the pairs by index. While iterating through s, check whether the current position matches the next replacement index. If the substring s[index:index+len(source)] equals the source, append the target to the result and skip ahead by the source length. Otherwise, copy the current character and continue. Sorting ensures replacements are processed in order, preventing conflicts and maintaining the “simultaneous” requirement. This technique mainly uses sequential traversal of the string combined with ordered processing through sorting. Time complexity is O(n + k log k) where k is the number of replacements, and space complexity is O(n) for the result builder.
Approach 2: Direct Index Mapping (O(n) time, O(n) space)
A faster strategy builds a direct lookup structure mapping each replacement index to its operation. Create a dictionary or array where map[index] stores the corresponding source and target. Then iterate through the string once. At each position i, check if a replacement begins there using a constant-time hash lookup. If present, verify that the substring matches the source; if it does, append the target and jump forward by the source length. Otherwise append the current character and move forward by one. This eliminates the sorting step and relies on efficient hash table lookups and linear traversal of the array of indices. The algorithm runs in O(n) time with O(n) additional space for the result and mapping.
Recommended for interviews: The direct index mapping approach is typically expected because it achieves linear time with a clean single pass. The sorting approach still demonstrates solid reasoning about ordered operations and is easier to derive during an interview. Showing both communicates strong understanding: sorting proves you can structure the operations correctly, while index mapping shows optimization using hash-based lookup.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simultaneous Replacement using Sorting | O(n + k log k) | O(n) | When operations must be processed in order and you want a straightforward implementation. |
| Direct Index Mapping | O(n) | O(n) | Best general solution; avoids sorting and performs replacements in a single pass. |