833. Find And Replace in String

• Time: $O(n\log n + n|\texttt{s}|)$, where $n = |\texttt{indices}|$
• Space: $O(n + |\texttt{s}|)$

C++JavaPython

class Solution {
 public:
  string findReplaceString(string s, vector<int>& indices,
                           vector<string>& sources, vector<string>& targets) {
    vector<pair<int, int>> 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;
  }
};

class Solution {
  public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
    List<Pair<Integer, Integer>> 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;
  }
}

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