#833

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find And Replace in String

This problem challenges you to perform multiple string replacements at specific indices using a pattern involving array scanning and hash lookup.

array hash table string sorting

Problem Statement

You are given a string s and three parallel arrays: indices, sources, and targets. Each element in the indices array represents the starting index where a replacement operation should occur. The corresponding source string in the sources array is checked, and if it matches the substring in s at that index, it is replaced with the target from the targets array.

Your task is to apply all the k replacement operations sequentially, modifying the string s according to the given indices, sources, and targets arrays. If the source at a given index doesn't match the substring in s, no replacement is made for that operation.

Examples

Example 1

Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]

Output: "eeebffff"

"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"

"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.

Solution Approach

Array Scanning with Hash Lookups

Iterate over the indices array. For each index, check if the substring in s starting from that index matches the source. If it matches, replace it with the corresponding target using array lookups. This approach ensures each replacement is efficient, with an overall time complexity based on the length of the string and the number of replacement operations.

Efficient String Modification

Instead of modifying the string s in place after each operation (which could be inefficient), construct a new string by replacing only those parts of s that need to be changed. This approach minimizes unnecessary string concatenations and optimizes the overall solution.

Handling Edge Cases

Handle cases where a source does not match the substring at a given index. In such cases, simply skip that replacement operation without modifying the string. Also, ensure the function works efficiently even when there are no replacements or when the indices go out of bounds.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity: O(k * m), where k is the number of replacement operations and m is the average length of the source strings. This comes from checking each source string for a match at the given index. Space complexity: O(n), where n is the length of the string s, as we create a new string after performing all replacements.

What Interviewers Usually Probe

Look for understanding of how to apply array scanning and hash lookup techniques for string modifications.
Assess how well the candidate handles edge cases where no replacements occur or where an index does not match.
Check for knowledge of optimizing string modifications, avoiding repeated concatenation within loops.

Common Pitfalls or Variants

Common pitfalls

Not checking if the source matches the substring before applying the replacement.
Modifying the string in place in an inefficient way, leading to unnecessary overhead.
Failing to handle cases where the source does not match the substring at a given index.

Follow-up variants

Using a hash map for faster lookups when there are many replacement operations.
Implementing the function with a greedy approach where you prioritize larger replacements first.
Performing all replacements in one pass through the string using a more advanced string manipulation algorithm.

FAQ

What is the time complexity of the Find And Replace in String problem?

The time complexity is O(k * m), where k is the number of operations, and m is the average length of the source strings.

How can I optimize the replacement process for Find And Replace in String?

Optimizing string modifications by avoiding repeated string concatenations and using a new string instead of modifying in place can greatly improve performance.

What if a source does not match the substring in the string?

If the source string does not match the substring at the given index, the replacement does not occur, and the string remains unchanged for that operation.

How do array scanning and hash lookups apply to this problem?

Array scanning helps iterate through indices, and hash lookups can be used for efficiently checking and replacing substrings in the main string.

What are common edge cases in the Find And Replace in String problem?

Edge cases include situations where no replacements occur, where the source does not match at a given index, and handling out-of-bounds indices.

terminal

Solution

Solution 1: Simulation

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def findReplaceString(
        self, s: str, indices: List[int], sources: List[str], targets: List[str]
    ) -> str:
        n = len(s)
        d = [-1] * n
        for k, (i, src) in enumerate(zip(indices, sources)):
            if s.startswith(src, i):
                d[i] = k
        ans = []
        i = 0
        while i < n:
            if ~d[i]:
                ans.append(targets[d[i]])
                i += len(sources[d[i]])
            else:
                ans.append(s[i])
                i += 1
        return "".join(ans)

Continue Practicing

#792 number of matching subsequences #893 groups of special equivalent strings #721 accounts merge