How to replace a substring of a string
Given three strings S, S1, and S2 consisting of N, M, and K characters respectively, the task is to modify the string S by replacing all the substrings S1 with the string S2 in the string S.
Examples:
Input: S = “abababa”, S1 = “aba”, S2 = “a”
Output: aba
Explanation:
Change the substrings S[0, 2] and S[4, 6](= S1) to the string S2(= “a”) modifies the string S to “aba”. Therefore, print “aba”.Input: S = “w3wiki”, S1 = “eek”, S2 = “ok”
Output: goksforgoks
Naive Approach: The simplest approach to solve the given problem is to traverse the string S and when any string S1 is found as a substring in the string S then replace it by S2. Follow the steps below to solve this problem:
- Initialize a string ans to store the resultant string after replacing all the occurrences of the substring S1 to S2 in the string S.
- Iterate over the characters of the string S using variable i and perform the following steps:
- If the prefix substring of the string S is equal to S1 from the index i, then add the string S2 in the string ans.
- Otherwise, add the current character to the string ans.
- After completing the above steps, print the string ans as the result.
Below is the implementation of the above approach:
C
#include <stdio.h> #include <string.h> // Function to replace all the occurrences // of the substring S1 to S2 in string S void modifyString( char * s, char * s1, char * s2) { // Stores the resultant string char ans[1000] = { 0 }; int ans_idx = 0; // Traverse the string s for ( int i = 0; i < strlen (s); i++) { int k = 0; // If the first character of // string s1 matches with the // current character in string s if (s[i] == s1[k] && i + strlen (s1) <= strlen (s)) { int j; // If the complete string // matches or not for (j = i; j < i + strlen (s1); j++) { if (s[j] != s1[k]) { break ; } else { k = k + 1; } } // If complete string matches // then replace it with the // string s2 if (j == i + strlen (s1)) { for ( int l = 0; l < strlen (s2); l++) { ans[ans_idx++] = s2[l]; } i = j - 1; } // Otherwise else { ans[ans_idx++] = s[i]; } } // Otherwise else { ans[ans_idx++] = s[i]; } } // Print the resultant string printf ( "%s" , ans); } // Driver Code int main() { char S[] = "w3wiki" ; char S1[] = "eek" ; char S2[] = "ok" ; modifyString(S, S1, S2); return 0; } |
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to replace all the occurrences // of the substring S1 to S2 in string S void modifyString(string& s, string& s1, string& s2) { // Stores the resultant string string ans = "" ; // Traverse the string s for ( int i = 0; i < s.length(); i++) { int k = 0; // If the first character of // string s1 matches with the // current character in string s if (s[i] == s1[k] && i + s1.length() <= s.length()) { int j; // If the complete string // matches or not for (j = i; j < i + s1.length(); j++) { if (s[j] != s1[k]) { break ; } else { k = k + 1; } } // If complete string matches // then replace it with the // string s2 if (j == i + s1.length()) { ans.append(s2); i = j - 1; } // Otherwise else { ans.push_back(s[i]); } } // Otherwise else { ans.push_back(s[i]); } } // Print the resultant string cout << ans; } // Driver Code int main() { string S = "w3wiki" ; string S1 = "eek" ; string S2 = "ok" ; modifyString(S, S1, S2); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to replace all the occurrences // of the subString S1 to S2 in String S static void modifyString(String s, String s1, String s2) { // Stores the resultant String String ans = "" ; // Traverse the String s for ( int i = 0 ; i < s.length(); i++) { int k = 0 ; // If the first character of // String s1 matches with the // current character in String s if (s.charAt(i) == s1.charAt(k) && i + s1.length() <= s.length()) { int j; // If the complete String // matches or not for (j = i; j < i + s1.length(); j++) { if (s.charAt(j) != s1.charAt(k)) { break ; } else { k = k + 1 ; } } // If complete String matches // then replace it with the // String s2 if (j == i + s1.length()) { ans += (s2); i = j - 1 ; } // Otherwise else { ans += (s.charAt(i)); } } // Otherwise else { ans += (s.charAt(i)); } } // Print the resultant String System.out.print(ans); } // Driver Code public static void main(String[] args) { String S = "w3wiki" ; String S1 = "eek" ; String S2 = "ok" ; modifyString(S, S1, S2); } } // This code is contributed by gauravrajput1 |
Python3
# Python program for the above approach # Function to replace all the occurrences # of the substring S1 to S2 in string S def modifyString(s, s1, s2): # Stores the resultant string ans = "" # Traverse the string s i = 0 while i < len (s): k = 0 # If the first character of string s1 matches with the # current character in string s if s[i] = = s1[k] and i + len (s1) < = len (s): j = i # If the complete string matches or not while j < i + len (s1) and s[j] = = s1[k]: k + = 1 j + = 1 # If complete string matches then replace it with the string s2 if j = = i + len (s1): ans + = s2 i = j - 1 # Otherwise else : ans + = s[i] else : ans + = s[i] i + = 1 # Print the resultant string print (ans) # Driver Code S = "w3wiki" S1 = "eek" S2 = "ok" modifyString(S, S1, S2) # This code is contributed by rutikbhosale |
C#
// C# program for the above approach using System; public class GFG { // Function to replace all the occurrences // of the subString S1 to S2 in String S static void modifyString(String s, String s1, String s2) { // Stores the resultant String String ans = "" ; // Traverse the String s for ( int i = 0; i < s.Length; i++) { int k = 0; // If the first character of // String s1 matches with the // current character in String s if (s[i] == s1[k] && i + s1.Length <= s.Length) { int j; // If the complete String // matches or not for (j = i; j < i + s1.Length; j++) { if (s[j] != s1[k]) { break ; } else { k = k + 1; } } // If complete String matches // then replace it with the // String s2 if (j == i + s1.Length) { ans += (s2); i = j - 1; } // Otherwise else { ans += (s[i]); } } // Otherwise else { ans += (s[i]); } } // Print the resultant String Console.Write(ans); } // Driver Code public static void Main(String[] args) { String S = "w3wiki" ; String S1 = "eek" ; String S2 = "ok" ; modifyString(S, S1, S2); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript program for the above approach // Function to replace all the occurrences // of the sublet S1 to S2 in let S function modifylet(s, s1, s2) { // Stores the resultant let let ans = "" ; // Traverse the let s for (let i = 0; i < s.length; i++) { let k = 0; // If the first character of // let s1 matches with the // current character in let s if (s[i] == s1[k] && i + s1.length <= s.length) { let j; // If the complete let // matches or not for (j = i; j < i + s1.length; j++) { if (s[j] != s1[k]) { break ; } else { k = k + 1; } } // If complete let matches // then replace it with the // let s2 if (j == i + s1.length) { ans = ans + s2; i = j - 1; } // Otherwise else { ans = ans + s[i]; } } // Otherwise else { ans = ans + s[i]; } } // Print the resultant let document.write(ans); } // Driver Code let S = "w3wiki" ; let S1 = "eek" ; let S2 = "ok" ; modifylet(S, S1, S2); // This code is contributed by splevel62. </script> |
goksforgoks
Time Complexity: O(N*M)
Auxiliary Space: O(N)
Efficient Approach: The above approach can also be optimized by creating the longest proper prefix and suffix array for the string S1 and then perform the KMP Algorithm to find the occurrences of the string S1 in the string S. Follow the steps below to solve this problem:
- Create a vector, say lps[] that stores the longest proper prefix and suffix for each character and fill this vector using the KMP algorithm for the string S1.
- Initialize two variables say, i and j as 0 to store the position of current character in s and s1 respectively.
- Initialize a vector found to store all the starting indexes from which string S1 occurs in S.
- Iterate over the characters of the string S using variable i and perform the following steps:
- If S[i] is equal to S1[j], then increment i and j by 1.
- If j is equal to the length of s1, then add the value (i – j) to the vector found and update j as lps[j – 1].
- Otherwise, if the value of S[i] is not equal to S1[j], then if j is equal to 0, then increment the value of i by 1. Otherwise, update j as lps[j – 1].
- Initialize a variable say, prev as 0 to store the last changed index and an empty string ans to store the resultant string after replacing all the initial appearances of s1 by s2 in s.
- Traverse the vector found[] and if the value of found[i] is greater than prev, then add the string S2 in place of S1 in ans.
- After completing the above steps, print the string ans as the result.
Below is the implementation of the above approach:
C
#include <stdio.h> #include <string.h> // Function to calculate the LPS array // for the given string S1 void computeLPS( char * s1, int * lps) { // Stores the longest proper prefix // and suffix for each character // in the string s1 int len = 0; // Set lps value 0 for the first // character of the string s1 lps[0] = 0; int i = 1; // Iterate to fill the lps vector while (i < strlen (s1)) { if (s1[i] == s1[len]) { len = len + 1; lps[i] = len; i = i + 1; } else { // If there is no longest // proper prefix which is // suffix, then set lps[i] = 0 if (len == 0) { lps[i] = 0; i = i + 1; } // Otherwise else len = lps[len - 1]; } } } // Function to replace all the occurrences // of the substring S1 to S2 in string S void modifyString( char * s, char * s1, char * s2) { int n = strlen (s); int m = strlen (s1); int lps[m]; computeLPS(s1, lps); int i = 0; int j = 0; // Stores all the starting index // from character S1 occurs in S int found[n / m + 1]; int k = 0; // Iterate to find all starting // indexes and store all indices // in a found[] while (i < n) { if (s[i] == s1[j]) { i = i + 1; j = j + 1; } // The string s1 occurrence is // found and store it in found[] if (j == m) { found[k++] = i - j; j = lps[j - 1]; } else if (i < n && s1[j] != s[i]) { if (j == 0) i = i + 1; else j = lps[j - 1]; } } // Stores the resultant string char ans[n + k * ( strlen (s2) - m) + 1]; int prev = 0; int ans_len = 0; // Traverse the found[] for ( int l = 0; l < k; l++) { if (found[l] < prev) continue ; strncpy (ans + ans_len, s + prev, found[l] - prev); ans_len += found[l] - prev; strncpy (ans + ans_len, s2, strlen (s2)); ans_len += strlen (s2); prev = found[l] + m; } strncpy (ans + ans_len, s + prev, n - prev); ans_len += n - prev; ans[ans_len] = '\0' ; // Print the resultant string printf ( "%s\n" , ans); } // Driver Code int main() { char S[] = "w3wiki" ; char S1[] = "eek" ; char S2[] = "ok" ; modifyString(S, S1, S2); return 0; } |
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the LPS array // for the given string S1 vector< int > computeLPS(string& s1) { // Stores the longest proper prefix // and suffix for each character // in the string s1 vector< int > lps(s1.length()); int len = 0; // Set lps value 0 for the first // character of the string s1 lps[0] = 0; int i = 1; // Iterate to fill the lps vector while (i < s1.length()) { if (s1[i] == s1[len]) { len = len + 1; lps[i] = len; i = i + 1; } else { // If there is no longest // proper prefix which is // suffix, then set lps[i] = 0 if (len == 0) { lps[i] = 0; i = i + 1; } // Otherwise else len = lps[len - 1]; } } return lps; } // Function to replace all the occurrences // of the substring S1 to S2 in string S void modifyString(string& s, string& s1, string& s2) { vector< int > lps = computeLPS(s1); int i = 0; int j = 0; // Stores all the starting index // from character S1 occurs in S vector< int > found; // Iterate to find all starting // indexes and store all indices // in a vector found while (i < s.length()) { if (s[i] == s1[j]) { i = i + 1; j = j + 1; } // The string s1 occurrence is // found and store it in found[] if (j == s1.length()) { found.push_back(i - j); j = lps[j - 1]; } else if (i < s.length() && s1[j] != s[i]) { if (j == 0) i = i + 1; else j = lps[j - 1]; } } // Stores the resultant string string ans = "" ; int prev = 0; // Traverse the vector found[] for ( int k = 0; k < found.size(); k++) { if (found[k] < prev) continue ; ans.append(s.substr(prev, found[k] - prev)); ans.append(s2); prev = found[k] + s1.size(); } ans.append(s.substr(prev, s.length() - prev)); // Print the resultant string cout << ans << endl; } // Driver Code int main() { string S = "w3wiki" ; string S1 = "eek" ; string S2 = "ok" ; modifyString(S, S1, S2); return 0; } |
Java
// Java program for the above approach import java.util.ArrayList; class Replace { // Function to calculate the LPS array // for the given string S1 static int [] computeLPS(String s1) { // Stores the longest proper prefix // and suffix for each character // in the string s1 int [] lps = new int [s1.length()]; int len = 0 ; // Set lps value 0 for the first // character of the string s1 lps[ 0 ] = 0 ; int i = 1 ; // Iterate to fill the lps vector while (i < s1.length()) { if (s1.charAt(i) == s1.charAt(len)) { len = len + 1 ; lps[i] = len; i = i + 1 ; } else { // If there is no longest // proper prefix which is // suffix, then set lps[i] = 0 if (len == 0 ) { lps[i] = 0 ; i = i + 1 ; } // Otherwise else len = lps[len - 1 ]; } } return lps; } // Function to replace all the occurrences // of the substring S1 to S2 in string S static void modifyString(String s, String s1, String s2) { int [] lps = computeLPS(s1); int i = 0 ; int j = 0 ; // Stores all the starting index // from character S1 occurs in S ArrayList<Integer> found = new ArrayList<>(); // Iterate to find all starting // indexes and store all indices // in a vector found while (i < s.length()) { if (s.charAt(i) == s1.charAt(j)) { i = i + 1 ; j = j + 1 ; } // The string s1 occurrence is // found and store it in found[] if (j == s1.length()) { found.add(i - j); j = lps[j - 1 ]; } else if (i < s.length() && s1.charAt(j) != s.charAt(i)) { if (j == 0 ) i = i + 1 ; else j = lps[j - 1 ]; } } // Stores the resultant string String ans = "" ; int prev = 0 ; // Traverse the vector found[] for ( int k = 0 ; k < found.size(); k++) { if (found.get(k) < prev) continue ; ans += s.substring(prev, found.get(k)); ans += s2; prev = found.get(k) + s1.length(); } ans += s.substring(prev, s.length()); // Print the resultant string System.out.println(ans); } // Driver Code public static void main (String[] args) { String S = "w3wiki" ; String S1 = "eek" ; String S2 = "ok" ; modifyString(S, S1, S2); } } // This code is contributed by Ajax |
Python3
# Python program for the above approach # Function to calculate the LPS array # for the given string S1 def computeLPS(s1): # Stores the longest proper prefix # and suffix for each character # in the string s1 lps = [ 0 ] * len (s1) length = 0 # Set lps value 0 for the first # character of the string s1 lps[ 0 ] = 0 i = 1 # Iterate to fill the lps vector while i < len (s1): if s1[i] = = s1[length]: length + = 1 lps[i] = length i + = 1 else : # If there is no longest # proper prefix which is # suffix, then set lps[i] = 0 if length = = 0 : lps[i] = 0 i + = 1 # Otherwise else : length = lps[length - 1 ] return lps # Function to replace all the occurrences # of the substring S1 to S2 in string S def modifyString(s, s1, s2): lps = computeLPS(s1) i = j = 0 # Stores all the starting index # from character S1 occurs in S found = [] # Iterate to find all starting # indexes and store all indices # in a list found while i < len (s): if s[i] = = s1[j]: i + = 1 j + = 1 # The string s1 occurrence is # found and store it in found[] if j = = len (s1): found.append(i - j) j = lps[j - 1 ] elif i < len (s) and s1[j] ! = s[i]: if j = = 0 : i + = 1 else : j = lps[j - 1 ] # Stores the resultant string ans = "" prev = 0 # Traverse the list found[] for k in range ( len (found)): if found[k] < prev: continue ans + = s[prev:found[k]] ans + = s2 prev = found[k] + len (s1) ans + = s[prev:] # Print the resultant string print (ans) # Driver Code S = "w3wiki" S1 = "eek" S2 = "ok" modifyString(S, S1, S2) # This code is contributed by rutikbhosale |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to calculate the LPS array // for the given string S1 static List< int > ComputeLPS( string s1) { // Stores the longest proper prefix // and suffix for each character // in the string s1 List< int > lps = new List< int >(s1.Length); int len = 0; // Set lps value 0 for the first // character of the string s1 lps.Add(0); int i = 1; // Iterate to fill the lps vector while (i < s1.Length) { if (s1[i] == s1[len]) { len = len + 1; lps.Add(len); i = i + 1; } else { // If there is no longest // proper prefix which is // suffix, then set lps[i] = 0 if (len == 0) { lps.Add(0); i = i + 1; } // Otherwise else len = lps[len - 1]; } } return lps; } // Function to replace all the occurrences // of the substring S1 to S2 in string S static void ModifyString( string s, string s1, string s2) { List< int > lps = ComputeLPS(s1); int i = 0; int j = 0; // Stores all the starting index // from character S1 occurs in S List< int > found = new List< int >(); // Iterate to find all starting // indexes and store all indices // in a list found while (i < s.Length) { if (s[i] == s1[j]) { i = i + 1; j = j + 1; } // The string s1 occurrence is // found and store it in found[] if (j == s1.Length) { found.Add(i - j); j = lps[j - 1]; } else if (i < s.Length && s1[j] != s[i]) { if (j == 0) i = i + 1; else j = lps[j - 1]; } } // Stores the resultant string string ans = "" ; int prev = 0; // Traverse the list found[] for ( int k = 0; k < found.Count; k++) { if (found[k] < prev) continue ; ans += s.Substring(prev, found[k] - prev); ans += s2; prev = found[k] + s1.Length; } ans += s.Substring(prev, s.Length - prev); // Print the resultant string Console.WriteLine(ans); } // Driver Code static void Main() { string S = "w3wiki" ; string S1 = "eek" ; string S2 = "ok" ; ModifyString(S, S1, S2); } } // This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript program for the above approach // Function to calculate the LPS array // for the given string S1 function computeLPS(s1) { // Stores the longest proper prefix // and suffix for each character // in the string s1 let lps = new Array(s1.length).fill(0); let len = 0; // Set lps value 0 for the first // character of the string s1 lps[0] = 0; let i = 1; // Iterate to fill the lps vector while (i < s1.length) { if (s1[i] == s1[len]) { len = len + 1; lps[i] = len; i = i + 1; } else { // If there is no longest // proper prefix which is // suffix, then set lps[i] = 0 if (len == 0) { lps[i] = 0; i = i + 1; } // Otherwise else len = lps[len - 1]; } } return lps; } // Function to replace all the occurrences // of the substring S1 to S2 in string S function modifyString(s, s1, s2) { let lps = computeLPS(s1); let i = 0; let j = 0; // Stores all the starting index // from character S1 occurs in S let found = []; // Iterate to find all starting // indexes and store all indices // in a vector found while (i < s.length) { if (s[i] == s1[j]) { i = i + 1; j = j + 1; } // The string s1 occurrence is // found and store it in found[] if (j == s1.length) { found.push(i - j); j = lps[j - 1]; } else if (i < s.length && s1[j] != s[i]) { if (j == 0) i = i + 1; else j = lps[j - 1]; } } // Stores the resultant string let ans = "" ; let prev = 0; // Traverse the vector found[] for (let k = 0; k < found.length; k++) { if (found[k] < prev) continue ; ans = ans + s.substring(prev, found[k]); ans = ans + s2; prev = found[k] + s1.length; } ans = ans + s.substring(prev, s.length); // Print the resultant string console.log(ans); } // Driver Code let S = "w3wiki" ; let S1 = "eek" ; let S2 = "ok" ; modifyString(S, S1, S2); |
goksforgoks
Time Complexity: O(N + M)
Auxiliary Space: O(N)
Contact Us