# 833. Find And Replace in String

• Time: $O(n\log n + n|\texttt{s}|)$, where $n = |\texttt{indices}|$
• Space: $O(n + |\texttt{s}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: string findReplaceString(string s, vector& indices, vector& sources, vector& targets) { vector> sortedIndices; for (int i = 0; i < indices.size(); ++i) sortedIndices.emplace_back(indices[i], i); sort(rbegin(sortedIndices), rend(sortedIndices)); for (const auto& [index, i] : sortedIndices) { const string& source = sources[i]; const string& target = targets[i]; if (s.substr(index, source.length()) == source) s = s.substr(0, index) + target + s.substr(index + source.length()); } return s; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) { List> sortedIndices = new ArrayList<>(); for (int i = 0; i < indices.length; ++i) sortedIndices.add(new Pair<>(indices[i], i)); Collections.sort(sortedIndices, (a, b) -> b.getKey() - a.getKey()); for (var sortedIndex : sortedIndices) { final int index = sortedIndex.getKey(); final int i = sortedIndex.getValue(); final String source = sources[i]; final String target = targets[i]; if (s.substring(index, index + source.length()).equals(source)) s = s.substring(0, index) + target + s.substring(index + source.length()); } return s; } } 
 1 2 3 4 5 6 7 class Solution: def findReplaceString(self, s: str, indexes: List[int], sources: List[str], targets: List[str]) -> str: for index, source, target in sorted(zip(indexes, sources, targets), reverse=True): if s[index:index + len(source)] == source: s = s[:index] + target + s[index + len(source):] return s