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[] = {“neveropen”, “neveropen”}
Output: neveropen
Explanation: “g” starts at index 0, so, it’s replaced by “neveropen”.
Similarly, “ks” starts at index 4, and is replaced by “neveropen”.Input: S = “gforks”, Q = 2, index[] = {0, 3}, sources[] = {“g”, “ss”}, targets[] = {“neveropen”, “neveropen”}
Output: neveropenforks
Explanation: “g” starts at index 0, so, it’s replaced by “neveropen”.
“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++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find and Replace in Stringstring findAndReplace(string S, int Q, int index[], string sources[], string targets[]){ string ans; int space = 0; for (int i = 0; i < Q; i++) { // Add the substring from the original string // to the answer string ans += S.substr(ans.size() - space, index[i] - ans.size() + space); // Check if given condition satisfies or not if (S.substr(index[i], sources[i].size()) == sources[i]) { // Substitute the source with the target space += targets[i].size() - sources[i].size(); // Add extra space in the space variable ans += targets[i]; } } ans += S.substr(ans.size() - space); return ans;}// Driver codeint main(){ string S; S = "gforks"; int Q = 2; int index[] = { 0, 4 }; string sources[] = { "g", "ks" }; string targets[] = { "neveropen", "neveropen" }; // Function call cout << findAndReplace(S, Q, index, sources, targets); return 0;} |
Java
// Java Code for the above approachpublic class GFG{ // Function to find and Replace in String static String findAndReplace(String S, int Q, int[] index, String[] sources, String[] targets) { String ans=""; int space = 0; for (int i = 0; i < Q; i++) { // Add the substring from the original string // to the answer string ans += S.substring(ans.length() - space,index[i]); // Check if given condition satisfies or not if ((S.substring(index[i], index[i] + sources[i].length())).equals(sources[i])) { // Substitute the source with the target space += targets[i].length() - sources[i].length(); // Add extra space in the space variable ans += targets[i]; } } ans += S.substring(ans.length() - space); return ans; } public static void main (String []args){ // Code String S; S = "gforks"; int Q = 2; int[] index = { 0, 4 }; String[] sources = { "g", "ks" }; String[] targets = { "neveropen", "neveropen" }; // Function call System.out.println(findAndReplace(S, Q, index, sources, targets)); }}// This code is contributed by AnkThon |
Python3
# python3 code for the above approach# Function to find and Replace in Stringdef findAndReplace(S, Q, index, sources, targets) : ans="" space = 0 for i in range(0,Q) : # Add the substring from the original string # to the answer string ans += S[len(ans) - space : index[i]] # Check if given condition satisfies or not if S[index[i] : index[i] + len(sources[i])] == sources[i] : # Substitute the source with the target space += len(targets[i]) - len(sources[i]) # Add extra space in the space variable ans += targets[i] ans += S[len(ans) - space :] return ans# Driver codeif __name__ == "__main__" : S = "gforks" Q = 2 index = [ 0, 4 ] sources = [ "g", "ks" ] targets = [ "neveropen", "neveropen" ] # Function call print(findAndReplace(S, Q, index, sources, targets))# This code is contributed by adityapatil12 |
C#
using System;public class GFG{ // Function to find and Replace in String static String findAndReplace(String S, int Q, int[] index, String[] sources, String[] targets) { String ans=""; int space = 0; for (int i = 0; i < Q; i++) { // Add the substring from the original string // to the answer string ans += S.Substring(ans.Length - space, index[i] - ans.Length + space); // Check if given condition satisfies or not if (S.Substring(index[i], sources[i].Length) == sources[i]) { // Substitute the source with the target space += targets[i].Length - sources[i].Length; // Add extra space in the space variable ans += targets[i]; } } ans += S.Substring(ans.Length - space); return ans; } public static void Main (){ // Code String S; S = "gforks"; int Q = 2; int[] index = { 0, 4 }; string[] sources = { "g", "ks" }; string[] targets = { "neveropen", "neveropen" }; // Function call string ans = findAndReplace(S, Q, index, sources, targets); Console.Write(ans); }}// This code is contributed by akashish_. |
Javascript
<script> function findAndReplace(S, Q, index,sources,targets){ let ans=""; let space = 0; for (let i = 0; i < Q; i++) { // Add the substring from the original string // to the answer string ans += S.substr(ans.length - space, index[i] - ans.length + space); // Check if given condition satisfies or not if (S.substr(index[i], sources[i].length) == sources[i]) { // Substitute the source with the target space += targets[i].length - sources[i].length; // Add extra space in the space variable ans += targets[i]; } } ans += S.substr(ans.length - space); return ans;}// Driver code let S; S = "gforks"; let Q = 2; const index = [ 0, 4 ]; const sources = [ "g", "ks" ]; const targets = [ "neveropen", "neveropen" ]; // Function call console.log(findAndReplace(S, Q, index, sources, targets)); // This code is contributed by akashish_.</script> |
Output
neveropen
Time Complexity: O(|S| * Q)
Auxiliary Space: O(Q)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
