Skip to main content
Talentd

Find And Replace in String - Solution & Explanation

MediumArrayHash TableStringSorting13 min readAsked at: Google, Bloomberg
Practice this problem

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:

  1. Check if the substring sources[i] occurs at index indices[i] in the original string s.
  2. If it does not occur, do nothing.
  3. 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], and sources = ["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 <= 1000
  • k == indices.length == sources.length == targets.length
  • 1 <= k <= 100
  • 0 <= indexes[i] < s.length
  • 1 <= sources[i].length, targets[i].length <= 50
  • s consists of only lowercase English letters.
  • sources[i] and targets[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.

Approach 1: Approach 1: Simultaneous Replacement using Sorting

Sort replacement operations based on indices to ensure they are handled in the correct order. This method involves performing a right-to-left replacement such that indices remain unaffected.

This C solution leverages sorting to handle replacements from right to left, ensuring index integrity. A custom structure holds replacement details and a qsort function sorts them based on indices in descending order. After sorting, the program performs replacements where valid, preserving the order of operations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O((k + m) log k) where m is the maximum mismatch length.
Space Complexity: O(n + k) where n is the length of the given string.

Try this approach in the editor →

Approach 2: Approach 2: Direct Index Mapping

Utilize an array to directly map changes to their respective indices. This way, valid operations can be done directly on the array without affecting others.

Utilizing a list to represent the string avoids mutability issues. Each valid replacement modifies the list directly, keeping replacements straightforward and simultaneous.

Code

PythonJavaScriptJava

Python

JavaScript

Java

Complexity

Time Complexity: O(n*k) worst case as each replacement traverses through the string length.
Space Complexity: O(n), determined by the additional list copy of the input string.

Try this approach in the editor →

Approach 3: Simulation

We iterate through each replacement operation. For the current k-th replacement operation (i, src), if s[i..i+|src|-1] is equal to src, we record that the string at index i needs to be replaced with the k-th string in targets; otherwise, no replacement is needed.

Next, we only need to iterate through the original string s and perform the replacements based on the recorded information.

The time complexity is O(L), and the space complexity is O(n), where L is the sum of the lengths of all strings, and n is the length of the string s.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Simultaneous Replacement using Sorting

Time Complexity: O((k + m) log k) where m is the maximum mismatch length.
Space Complexity: O(n + k) where n is the length of the given string.

Approach 2: Direct Index Mapping

Time Complexity: O(n*k) worst case as each replacement traverses through the string length.
Space Complexity: O(n), determined by the additional list copy of the input string.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simultaneous Replacement using SortingO(n + k log k)O(n)When operations must be processed in order and you want a straightforward implementation.
Direct Index MappingO(n)O(n)Best general solution; avoids sorting and performs replacements in a single pass.

Video Solution

Google Coding Interview Question | Leetcode 833 | Find And Replace in String • WorkWithGoogler • 4,881 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Find And Replace in String easy or hard?
Find And Replace in String is considered a medium-level problem. The main challenge is handling replacements simultaneously while maintaining correct indices and avoiding overlapping or incorrect substitutions.
Find And Replace in String Python/Java solution
Python solutions often use a dictionary mapping indices to (source, target) pairs and build the result using a list for efficient concatenation. Java implementations typically use a HashMap with a StringBuilder to construct the final string while iterating through the input.
How to solve Find And Replace in String in O(n)?
Create a hash map that maps each replacement index to its source and target strings. Traverse the original string from left to right. When the current index exists in the map and the source substring matches, append the target and jump ahead by the source length; otherwise append the current character.
What is the best approach for Find And Replace in String?
The direct index mapping approach is typically the best. It stores each replacement operation in a hash map keyed by its starting index, allowing a single pass through the string. Each position performs a constant-time lookup to check for replacements, producing an overall O(n) time complexity.
Is Find And Replace in String asked at Google/Amazon/Meta?
Problems involving simultaneous replacements and indexed string operations appear in interviews at companies like Google, Amazon, and Meta. They test string manipulation, careful indexing, and the ability to design efficient single-pass algorithms.
What data structure is used in Find And Replace in String?
Common solutions use arrays for the indices and a hash table (dictionary) to map indices to replacement operations. The algorithm also relies on sequential string traversal and sometimes sorting to process replacements in order.
What is the time complexity of Find And Replace in String?
The optimal solution runs in O(n) time using an index-to-replacement mapping and a single traversal of the string. A common alternative sorts the replacement operations first, leading to O(n + k log k) time where k is the number of replacements.

Ready to solve this problem?

Practice Find And Replace in String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays