Problem statement

https://leetcode.com/problems/find-and-replace-in-string/

Solution

Let us create dictionary d, where for each i we correspond it to S[i]. Then we iterate through zip(indexes, sources, targets) and if we have match, we change values in d: make d[i] = targ and make all others empty. In this way we can be sure that we store the original indexes.

Complexity

Time complexity is O(S + T), where S is total lenght of sources and T is total lenght of targets. Space complexity is O(T + n).

Code

class Solution:
    def findReplaceString(self, S, indexes, sources, targets):
        d = {i:S[i] for i in range(len(S))}
        for i, sour, targ in zip(indexes, sources, targets):
            if S[i:i+len(sour)] == sour:
                d[i] = targ
                for j in range(i+1, i + len(sour)): d[j] = ""

        return "".join(d[i] for i in range(len(S)))