To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).
Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y.  The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y.  If not, we do nothing.
For example, if we have S = "abcd" and we have some replacement operation i = 2, x = "cd", y = "ffff", then because "cd" starts at position 2 in the original string S, we will replace it with "ffff".
Using another example on S = "abcd", if we have both the replacement operation i = 0, x = "ab", y = "eee", as well as another replacement operation i = 2, x = "ec", y = "ffff", this second operation does nothing because in the original string S[2] = 'c', which doesn't match x[0] = 'e'.
All these operations occur simultaneously.  It's guaranteed that there won't be any overlap in replacement: for example, S = "abc", indexes = [0, 1], sources = ["ab","bc"] is not a valid test case.
Example 1:
Input: S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
Output: "eeebffff"
Explanation: "a" starts at index 0 in S, so it's replaced by "eee".
"cd" starts at index 2 in S, so it's replaced by "ffff".

Example 2:
Input: S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation: "ab" starts at index 0 in S, so it's replaced by "eee". 
"ec" doesn't starts at index 2 in the original S, so we do nothing.

Notes:

0 <= indexes.length = sources.length = targets.length <= 100
0 < indexes[i] < S.length <= 1000
All characters in given inputs are lowercase letters.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Sorting

Data structures

Starter code: class Solution:
    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
        

Solutions:
class Solution:

	def findReplaceString(self, s: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
		l = []
		for (i, tgt, rpl) in zip(indexes, sources, targets):
			if s[i:i + len(tgt)] == tgt:
				l.append((i, tgt, rpl))
		l.sort()
		j = 0
		s = list(s)
		for (i, tgt, rpl) in l:
			s[i + j:i + j + len(tgt)] = rpl
			j += len(rpl) - len(tgt)
		return ''.join(s)


class Solution:

	def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
		sources_dict = {}
		targets_dict = {}
		for (i, pos_index) in enumerate(indexes):
			sources_dict[pos_index] = sources[i]
			targets_dict[pos_index] = targets[i]
		indexes.sort(reverse=True)
		for pos_index in indexes:
			source = sources_dict[pos_index]
			target = targets_dict[pos_index]
			tmp_str = S[pos_index:pos_index + len(source)]
			if tmp_str == source:
				S = S[:pos_index] + target + S[pos_index + len(source):]
		return S


class Solution:

	def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
		for (i, s, t) in sorted(zip(indexes, sources, targets), reverse=True):
			if S[i:i + len(s)] == s:
				S = S[:i] + t + S[i + len(s):]
		return S


class Solution:

	def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
		(result, offset) = (S, 0)
		for (i, s, t) in sorted(zip(indexes, sources, targets)):
			if S[i:i + len(s)] == s:
				result = result[:offset + i] + t + result[offset + i + len(s):]
				offset += len(t) - len(s)
		return result


class Solution:

	def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
		s_dict = {}
		t_dict = {}
		for (i, index) in enumerate(indexes):
			s_dict[index] = sources[i]
			t_dict[index] = targets[i]
		indexes.sort(reverse=True)
		for index in indexes:
			sour = s_dict[index]
			targ = t_dict[index]
			le_s = len(sour)
			tmp_str = S[index:index + le_s]
			if tmp_str == sour:
				S = S[:index] + targ + S[index + le_s:]
		return S


class Solution:

	def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
		S = list(S)
		for (i, s, t) in sorted(zip(indexes, sources, targets), reverse=True):
			appl = all([i + ind < len(S) and S[i + ind] == s[ind] for ind in range(len(s))])
			if appl:
				S[i:i + len(s)] = list(t)
		return ''.join(S)


class Solution:

	def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
		index_position = dict()
		r_list = []
		for (pos, index) in enumerate(indexes):
			source_len = len(sources[pos])
			if S[index:index + source_len] == sources[pos]:
				index_position[index] = pos
		next_index = 0
		for i in range(len(S)):
			if i < next_index:
				continue
			if i in index_position:
				pos = index_position[i]
				r_list.append(targets[pos])
				next_index += len(sources[pos])
			else:
				r_list.append(S[i])
				next_index += 1
		return ''.join(r_list)


class Solution:

	def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
		idx_og = 0
		idx_res = 0
		res = S
		for (index, source, target) in sorted(zip(indexes, sources, targets)):
			if S[index:index + len(source)] == source:
				index2 = index - idx_og + idx_res
				res = res[:index2] + target + res[index2 + len(source):]
				idx_og = index + len(source)
				idx_res = index2 + len(target)
		return res


class Solution:

	def check_source(self, start_idx, s, source):
		i = 0
		while i < len(source):
			if start_idx == len(s):
				return False
			if source[i] != s[start_idx]:
				return False
			start_idx += 1
			i += 1
		return True

	def findReplaceString(self, s: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
		res = []
		i = 0
		while i < len(s):
			if i in indexes:
				idx = indexes.index(i)
				source = sources[idx]
				target = targets[idx]
				if self.check_source(i, s, source):
					i += len(source)
					res.append(target)
					continue
			res.append(s[i])
			i += 1
		return ''.join(res)