{x}
blog image

Find And Replace in String

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.

Solution Explanation: Find And Replace in String

This problem requires performing multiple string replacements simultaneously without overlapping replacements affecting each other's indices. The solution involves a two-step process: identifying replacements and then applying them.

Approach:

  1. Identifying Replacements: We iterate through the indices, sources, and targets arrays. For each index i in indices, we check if the corresponding substring sources[k] exists at that index in the input string s. If it does, we store the index i and the corresponding target index k in a dictionary or array (d in the code examples). This ensures that we know which substring needs replacing and with what.

  2. Applying Replacements: We iterate through the input string s. If we encounter an index i that's marked for replacement in d, we append the corresponding targets[k] to the result. Otherwise, we append the original character s[i] to the result.

Time and Space Complexity Analysis:

  • Time Complexity: O(N + KM), where N is the length of the input string s, K is the number of replacement operations, and M is the maximum length of any substring in sources. The first step (identifying replacements) takes O(KM) because we potentially check for matches up to length M for each of the K operations. The second step (applying replacements) takes O(N) because we iterate through the string once.

  • Space Complexity: O(N), dominated by the space used for the resultant string. The auxiliary space used for d is O(N) in the worst case (all characters are replaced) and O(K) in the best case (no replacements). In practice, it will likely be between O(K) and O(N) depending on the number of replacements.

Code Explanation (Python):

class Solution:
    def findReplaceString(
        self, s: str, indices: List[int], sources: List[str], targets: List[str]
    ) -> str:
        n = len(s)
        d = [-1] * n  # Array to store replacement information (-1 means no replacement)
 
        # Step 1: Identifying Replacements
        for k, (i, src) in enumerate(zip(indices, sources)):
            if s.startswith(src, i): # Check if source substring exists at index i
                d[i] = k #Store the index i and target index k
 
        ans = [] # Build resultant string
        i = 0
        while i < n:
            if d[i] != -1: #If there is replacement at this index
                ans.append(targets[d[i]]) #Append the target string
                i += len(sources[d[i]]) #Advance the index by the length of the source string
            else:
                ans.append(s[i]) # Append the original character
                i += 1
 
        return "".join(ans) #Return the combined string

The other language implementations follow a similar logic, using appropriate data structures (arrays or hash maps) for efficient replacement tracking. The key is the two-step process of identifying and then applying the replacements while ensuring that the indexing doesn't get disrupted due to simultaneous operations.