Find And Replace in String

The problem requires you to replace certain substrings in a given string if they match with the source strings given. All replacements occur simultaneously and do not affect each other’s indices.

One way to solve this problem is by using a map data structure to store the mapping between indices and a pair of source and target strings. Then we can loop through the string. If the current index is in the map, we check if the source string matches the substring starting from the current index. If it does, we append the target string to our result and move the current index forward by the length of the source string. Otherwise, we append the current character to our result and move the current index forward by one.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        mapped = {indices[i]: (sources[i], targets[i]) for i in range(len(indices))}
        i = 0
        result = []
        while i < len(s):
            if i in mapped and s[i:i+len(mapped[i][0])] == mapped[i][0]:
                result.append(mapped[i][1])
                i += len(mapped[i][0])
            else:
                result.append(s[i])
                i += 1
        return ''.join(result)

This solution is efficient because it goes through the string only once, making its time complexity O(n), where n is the length of the string. It also uses O(k) extra space for the map, where k is the length of the indices array, so the space complexity is O(k).