algoadvance

Leetcode 833. Find And Replace in String

Problem Statement

You are given a string s and an array of indices. Each indices[i] indicates where a substring begins within s that you want to replace with another string. The list of source strings (sources[i]) and the list of target strings (targets[i]) are also provided.

To be more precise, if the substring in s starting at the index indices[i] and of length equal to len(sources[i]) matches sources[i], then you will replace that substring with targets[i]. If it doesn’t match, do nothing.

Return the modified string after all replacements have occurred.

Clarifying Questions

  1. Input Range:
    • Can indices be provided in any order, or will they always be sorted?
    • (Assuming any order) How do we handle overlapping replacements?
  2. Output:
    • Will there be any constraints on the length of s, indices, sources, or targets?

Let’s assume the following example inputs for further clarity:

Example

Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Output: "eeebffff"

Strategy

  1. Sort By Indices: To handle the replacements without affecting subsequent indices, we will sort the indices and the related sources and targets.
  2. Two-Pointer Technique: Use a pointer to traverse the string and reconstruct it while applying the replacements.
  3. String Matching: Check if the substring that starts at each index matches the source. If yes, append the target; otherwise, append the original character and move to the next index.

Code

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

std::string findReplaceString(std::string s, std::vector<int>& indices, std::vector<std::string>& sources, std::vector<std::string>& targets) {
    // Create a list of tuples (index, source, target) and sort them by index
    std::vector<std::tuple<int, std::string, std::string>> replacements;
    for (int i = 0; i < indices.size(); ++i) {
        replacements.emplace_back(indices[i], sources[i], targets[i]);
    }
    std::sort(replacements.begin(), replacements.end());

    // Creat a result string builder
    std::string result;
    int lastIndex = 0;

    for (const auto& [index, source, target] : replacements) {
        // Append the non-modified parts to the result
        result.append(s.substr(lastIndex, index - lastIndex));

        // Check and replace the matching segment
        if (s.substr(index, source.size()) == source) {
            result.append(target);
            lastIndex = index + source.size();
        } else {
            // If no match, just skip to the next index
            lastIndex = index;
        }
    }

    // Append the rest of the original string
    result.append(s.substr(lastIndex));

    return result;
}

int main() {
    std::string s = "abcd";
    std::vector<int> indices = {0, 2};
    std::vector<std::string> sources = {"a", "cd"};
    std::vector<std::string> targets = {"eee", "ffff"};
    
    std::string updatedString = findReplaceString(s, indices, sources, targets);
    std::cout << updatedString << std::endl;  // Output: "eeebffff"
    
    return 0;
}

Time Complexity

Thus, the overall time complexity is dominated by the sorting step, resulting in:

O(n log n + m + k)

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI