Monday, June 27, 2022
HomeSoftware DevelopmentExchange the given Strings ranging from given indices

# Exchange the given Strings ranging 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 ` `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;` `}`

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

RELATED ARTICLES