Given a string S on which you want to carry out Q exchange operations.
Every alternative operation has 3 parameters: a beginning index i, a supply phrase x and a goal phrase y. The rule is that if x begins at place i within the unique string S, then exchange that incidence of x with y.
Be aware: All these operations happen concurrently. It’s assured that there gained’t be any overlap in alternative: for instance, S = “abc”, indexes = [0, 1], sources = [“ab”, “bc”] will not be a legitimate check case.
Examples:
Enter: S = “gforks”, Q = 2, index[] = {0, 4}, sources[] = {“g”, “ks”}, targets[] = {“geeks”, “geeks”}
Output: geeksforgeeks
Clarification: “g” begins at index 0, so, it’s reaplaced by “geeks”.
Equally, “ks” begins at index 4, and is changed by “geeks”.Enter: S = “gforks”, Q = 2, index[] = {0, 3}, sources[] = {“g”, “ss”}, targets[] = {“geeks”, “geeks”}
Output: geeksforks
Clarification: “g” begins at index 0, so, it’s changed by “geeks”.
“ss” doesn’t begin at index 3 within the unique S, so it’s not changed.
Method: The issue could be solved based mostly on the next thought:
Create an extra string and for each operation test if alternative is feasible. If doable, then make the adjustments.
Comply with the steps talked about beneath to implement the thought:
- Create an empty string ans to retailer the ultimate reply.
- Create a variable to depend the additional letters added within the ans string than the unique string.
- Run a loop to the variety of operations (Q) instances.
- For each ith alternative, add the substring from the unique string to the reply string such that the substring will not be part of the reply string but and the substring finish on the ith index of the unique string.
- Substitute the supply with the goal if alternative is feasible and replace the additional characters added.
- After completion of Q replacements, add the remaining portion of the unique string as it’s.
Under is the implementation of the above method.
C++
|
|
Time Complexity: O(|S| * Q)
Auxiliary House: O(Q)
