Replace the given Strings starting from given indices

Given a string S on which you need to perform Q replace operations.
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 replace that occurrence of x with y.

Note: 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.

Examples:

Input: S = “gforks”, Q = 2, index[] = {0, 4}, sources[] = {“g”, “ks”}, targets[] = {“geeks”, “geeks”}
Output: geeksforgeeks
Explanation: “g” starts at index 0, so, it’s reaplaced by “geeks”. 
Similarly, “ks” starts at index 4, and is replaced by “geeks”.

Input: S = “gforks”, Q = 2, index[] = {0, 3}, sources[] = {“g”, “ss”}, targets[] = {“geeks”, “geeks”}
Output: geeksforks
Explanation: “g” starts at index 0, so, it’s replaced by “geeks”. 
“ss” doesn’t start at index 3 in the original S, so it’s not replaced.

Approach: The problem can be solved based on the following idea:

Create an additional string and for every operation check if replacement is possible. If possible, then make the changes.

Follow the steps mentioned below to implement the idea:

  • Create an empty string ans to store the final answer.
  • Create a variable to count the extra letters added in the ans string than the original string.
  • Run a loop to the number of operations (Q) times.
    • For every ith replacement, add the substring from the original string to the answer string such that the substring is not a part of the answer string yet and the substring end at the ith index of the original string.
    • Substitute the source with the target if replacement is possible and update the extra characters added.
  • After completion of Q replacements, add the remaining portion of the original string as it is.

Below is the implementation of the above approach.

C++

  

#include <bits/stdc++.h>

using namespace std;

  

string findAndReplace(string S, int Q, int index[],

                      string sources[], string targets[])

{

    string ans;

    int space = 0;

    for (int i = 0; i < Q; i++) {

  

        

        

        ans += S.substr(ans.size() - space,

                        index[i] - ans.size() + space);

  

        

        if (S.substr(index[i], sources[i].size())

            == sources[i]) {

  

            

            space += targets[i].size() - sources[i].size();

  

            

            ans += targets[i];

        }

    }

    ans += S.substr(ans.size() - space);

    return ans;

}

  

int main()

{

    string S;

    S = "gforks";

  

    int Q = 2;

  

    int index[] = { 0, 4 };

    string sources[] = { "g", "ks" };

    string targets[] = { "geeks", "geeks" };

  

    

    cout << findAndReplace(S, Q, index, sources, targets);

    return 0;

}
Output

geeksforgeeks

Time Complexity:  O(|S| * Q)
Auxiliary Space: O(Q)

By Julio MarchiPosted on