Given two string S1 and S2. The task is to wrap every instance of string S2 in string S1 with some string on either side.
Note: Here we will use underscore(_) for the wrapping part. It can be anything as per need, for example some HTML tag, white space, etc.
Examples:
Input: S1 = “examwill be a examexam”, S2 = “exam”
Output: “_exam_will be a _examexam_”
Explanation:
String S2 is “exam“, so wrap occurrence of S2 with underscore. Since, last two occurrence overlaps(in string examexam), so merge both the occurrence and wrap by putting underscore to farther left and farther right of merged substring.
Input: str = “abcabcabcabc”, substr = “abc”
Output: “_abcabcabcabc_”
Approach: The idea is to simply get the location of all instances of string S2 in S1 and add underscore at either end of the occurrence and if two or more instances of S2 overlaps then, add underscore at either end of the merged substring. Below are the steps:
- Get the location of all instances of the string S2 in the main string S1. For that traverse string S1 one character at a time and call substring-matching function, find().
- Create a 2D array of locations(say arr[][]), where each subarray holds the starting and ending indices of a specific instance of the string S2 in the string S1.
- Merge the overlapping starting and ending index intervals stored in arr[][].
- After the above steps all the overlapping indexes are merged. Now traverse the given string and intervals at the same time and create a new string by wrapping underscores.
- Print the new string after the above step.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function Definitions vector<vector< int > > getLocations(string str, string subStr); vector<vector< int > > collapse( vector<vector< int > > locations); string underscorify(string str, vector<vector< int > > locations); // Function that creates the string by // wrapping the underscore string underscorifySubstring(string str, string subStr) { // Function Call to intervals of // starting and ending index vector<vector< int > > locations = collapse(getLocations(str, subStr)); // Function Call return underscorify(str, locations); } // Function finds all starting and ending // index of the substring in given string vector<vector< int > > getLocations(string str, string subStr) { vector<vector< int > > locations{}; int startIdx = 0; int L = subStr.length(); // Traverse string str while (startIdx < str.length()) { // Find substr int nextIdx = str.find(subStr, startIdx); // If location found, then insert // pair int location[] if (nextIdx != string::npos) { locations.push_back({ nextIdx, (nextIdx + L) }); // Update the start index startIdx = nextIdx + 1; } else { break ; } } return locations; } // Function to merge the locations // of substrings that overlap each // other or sit next to each other vector<vector< int > > collapse( vector<vector< int > > locations) { if (locations.empty()) { return locations; } // 2D vector to store the merged // location of substrings vector<vector< int > > newLocations{ locations[0] }; vector< int >* previous = &newLocations[0]; for ( int i = 1; i < locations.size(); i++) { vector< int >* current = &locations[i]; // Condition to check if the // substring overlaps if (current->at(0) <= previous->at(1)) { previous->at(1) = current->at(1); } else { newLocations.push_back(*current); previous = &newLocations[newLocations.size() - 1]; } } return newLocations; } // Function creates a new string with // underscores added at correct positions string underscorify(string str, vector<vector< int > > locations) { int locationsIdx = 0; int stringIdx = 0; bool inBetweenUnderscores = false ; vector<string> finalChars{}; int i = 0; // Traverse the string and check // in locations[] to append _ while (stringIdx < str.length() && locationsIdx < locations.size()) { if (stringIdx == locations[locationsIdx][i]) { // Insert underscore finalChars.push_back( "_" ); inBetweenUnderscores = !inBetweenUnderscores; // Increment location index if (!inBetweenUnderscores) { locationsIdx++; } i = i == 1 ? 0 : 1; } // Create string s string s(1, str[stringIdx]); // Push the created string finalChars.push_back(s); stringIdx++; } if (locationsIdx < locations.size()) { finalChars.push_back( "_" ); } else if (stringIdx < str.length()) { finalChars.push_back(str.substr(stringIdx)); } // Return the resultant string return accumulate(finalChars.begin(), finalChars.end(), string()); } // Driver Code int main() { // Given string S1 and S2 string S1 = "examwill be a examexam" ; string S2 = "exam" ; // Function Call cout << underscorifySubstring(S1, S2); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function that creates the string by // wrapping the underscore static String underscorifySubstring(String str, String subStr) { // Function Call to intervals of // starting and ending index List<List<Integer> > locations = collapse(getLocations(str, subStr)); // Function Call return underscorify(str, locations); } // Function finds all starting and ending // index of the substring in given string static List<List<Integer> > getLocations(String str, String subStr) { @SuppressWarnings ( "unchecked" ) List<List<Integer> > locations = new ArrayList(); int startIdx = 0 ; int L = subStr.length(); // Traverse string str while (startIdx < str.length()) { // Find substr int nextIdx = str.indexOf(subStr, startIdx); // If location found, then insert // pair int location[] if (nextIdx != - 1 ) { locations.add(Arrays.asList( new Integer[] { nextIdx, nextIdx + L })); // Update the start index startIdx = nextIdx + 1 ; } else { break ; } } return locations; } // Function to merge the locations // of substrings that overlap each // other or sit next to each other static List<List<Integer> > collapse(List<List<Integer> > locations) { if (locations.size() == 0 ) { return locations; } // 2D vector to store the merged // location of substrings @SuppressWarnings ( "unchecked" ) List<List<Integer> > newLocations = new ArrayList(); newLocations.add(locations.get( 0 )); List<Integer> previous = locations.get( 0 ); for ( int i = 1 ; i < locations.size(); i++) { List<Integer> current = locations.get(i); // Condition to check if the // substring overlaps if (current.get( 0 ) <= previous.get( 1 )) { previous.set( 1 , current.get( 1 )); } else { newLocations.add(current); previous = newLocations.get( newLocations.size() - 1 ); } } return newLocations; } // Function creates a new string with // underscores added at correct positions static String underscorify(String str, List<List<Integer> > locations) { int locationsIdx = 0 ; int stringIdx = 0 ; boolean inBetweenUnderscores = false ; StringBuilder finalChars = new StringBuilder(); int i = 0 ; // Traverse the string and check // in locations[] to append _ while (stringIdx < str.length() && locationsIdx < locations.size()) { if (stringIdx == locations.get(locationsIdx).get(i)) { // Insert underscore finalChars.append( "_" ); inBetweenUnderscores = !inBetweenUnderscores; // Increment location index if (!inBetweenUnderscores) { locationsIdx++; } i = i == 1 ? 0 : 1 ; } // Push the string finalChars.append(str.charAt(stringIdx)); stringIdx++; } if (locationsIdx < locations.size()) { finalChars.append( "_" ); } else if (stringIdx < str.length()) { finalChars.append(str.substring(stringIdx)); } // Return the resultant string return finalChars.toString(); } public static void main(String[] args) { // Given string S1 and S2 String S1 = "examwill be a examexam" ; String S2 = "exam" ; // Function Call System.out.print(underscorifySubstring(S1, S2)); } } // This code is contributed by jithin |
Python3
# Python program for the above approach # Function that creates the string by # wrapping the underscore def underscorify_substring(string, sub_str): # Function Call to intervals of starting and ending index locations = collapse(get_locations(string, sub_str)) # Function Call return underscorify(string, locations) # Function finds all starting and ending index of the substring in given string def get_locations(string, sub_str): locations = [] start_idx = 0 l = len (sub_str) # Traverse string while start_idx < len (string): # Find sub_str next_idx = string.find(sub_str, start_idx) # If location found, then insert pair int location[] if next_idx ! = - 1 : locations.append([next_idx, next_idx + l]) # Update the start index start_idx = next_idx + 1 else : break return locations # Function to merge the locations of substrings that overlap each other or sit next to each other def collapse(locations): if not locations: return locations # 2D list to store the merged location of substrings new_locations = [locations[ 0 ]] previous = locations[ 0 ] for i in range ( 1 , len (locations)): current = locations[i] # Condition to check if the substring overlaps if current[ 0 ] < = previous[ 1 ]: previous[ 1 ] = current[ 1 ] else : new_locations.append(current) previous = new_locations[ - 1 ] return new_locations # Function creates a new string with underscores added at correct positions def underscorify(string, locations): locations_idx = 0 string_idx = 0 in_between_underscores = False final_chars = [] i = 0 # Traverse the string and check in locations[] to append _ while string_idx < len (string) and locations_idx < len (locations): if string_idx = = locations[locations_idx][i]: # Insert underscore final_chars.append( "_" ) in_between_underscores = not in_between_underscores # Increment location index if not in_between_underscores: locations_idx + = 1 i = 1 if i = = 0 else 0 # Push the string final_chars.append(string[string_idx]) string_idx + = 1 if locations_idx < len (locations): final_chars.append( "_" ) elif string_idx < len (string): final_chars.append(string[string_idx:]) # Return the resultant string return "".join(final_chars) # Given string S1 and S2 s1 = "examwill be a examexam" s2 = "exam" # Function Call print (underscorify_substring(s1, s2)) # This code is contributed by rutikbhosale |
Javascript
// JavaScript program for the above approach // Function that creates the string by // wrapping the underscore function underscorify_substring(string, sub_str) { // Function Call to intervals of starting and ending index const locations = collapse(get_locations(string, sub_str)); // Function Call return underscorify(string, locations); } // Function finds all starting and ending index of the substring in given string function get_locations(string, sub_str) { const locations = []; let start_idx = 0; const l = sub_str.length; // Traverse string while (start_idx < string.length) { // Find sub_str const next_idx = string.indexOf(sub_str, start_idx); // If location found, then insert pair into locations[] if (next_idx != -1) { locations.push([next_idx, next_idx + l]); // Update the start index start_idx = next_idx + 1; } else { break ; } } return locations; } // Function to merge the locations of substrings that overlap each other or sit next to each other function collapse(locations) { if (!locations.length) { return locations; } // 2D array to store the merged location of substrings const new_locations = [locations[0]]; let previous = locations[0]; for (let i = 1; i < locations.length; i++) { const current = locations[i]; // Condition to check if the substring overlaps if (current[0] <= previous[1]) { previous[1] = current[1]; } else { new_locations.push(current); previous = new_locations[new_locations.length - 1]; } } return new_locations; } // Function creates a new string with underscores added at correct positions function underscorify(string, locations) { let locations_idx = 0; let string_idx = 0; let in_between_underscores = false ; const final_chars = []; let i = 0; // Traverse the string and check in locations[] to append _ while (string_idx < string.length && locations_idx < locations.length) { if (string_idx === locations[locations_idx][i]) { // Insert underscore final_chars.push( "_" ); in_between_underscores = !in_between_underscores; // Increment location index if (!in_between_underscores) { locations_idx++; } i = i === 0 ? 1 : 0; } // Push the string final_chars.push(string[string_idx]); string_idx++; } if (locations_idx < locations.length) { final_chars.push( "_" ); } else if (string_idx < string.length) { final_chars.push(string.slice(string_idx)); } // Return the resultant string return final_chars.join( "" ); } // Given string S1 and S2 const s1 = "examwill be a examexam" ; const s2 = "exam" ; // Function Call console.log(underscorify_substring(s1, s2)); // This code is contributed by rutikbhosale |
C#
using System; using System.Collections.Generic; // Define a class named GFG class GFG { // Define a static method to underscore the given // substring in the given string static string UnderscorifySubstring( string str, string subStr) { // Get the locations of all occurrences of the given // substring in the given string List<List< int > > locations = Collapse(GetLocations(str, subStr)); // Underscore the given substring in the given // string based on the locations of its occurrences return Underscorify(str, locations); } // Define a static method to get the locations of all // occurrences of the given substring in the given // string static List<List< int > > GetLocations( string str, string subStr) { // Initialize a list to store the locations of all // occurrences of the given substring in the given // string List<List< int > > locations = new List<List< int > >(); // Initialize the starting index for searching the // next occurrence of the given substring int startIdx = 0; // Get the length of the given substring int L = subStr.Length; // Loop until there are no more occurrences of the // given substring in the given string while (startIdx < str.Length) { // Get the index of the next occurrence of the // given substring in the given string int nextIdx = str.IndexOf(subStr, startIdx); // If the next occurrence of the given substring // is found if (nextIdx != -1) { // Add the start and end indices of the next // occurrence of the given substring to the // list of locations locations.Add( new List< int >{ nextIdx, nextIdx + L }); // Update the starting index for searching // the next occurrence of the given // substring startIdx = nextIdx + 1; } // If there are no more occurrences of the given // substring in the given string else { // Break out of the loop break ; } } // Return the list of locations of all occurrences // of the given substring in the given string return locations; } // Define a static method to collapse the overlapping // locations of all occurrences of the given substring // in the given string static List<List< int > > Collapse(List<List< int > > locations) { // If there are no locations to collapse if (locations.Count == 0) { // Return the original list of locations return locations; } // Initialize a new list to store the collapsed // locations List<List< int > > newLocations = new List<List< int > >(); // Add the first location to the new list newLocations.Add(locations[0]); // Initialize a variable to store the previous // location List< int > previous = locations[0]; // Loop through all the remaining locations for ( int i = 1; i < locations.Count; i++) { // Get the current location List< int > current = locations[i]; // If the current location overlaps with the // previous location if (current[0] <= previous[1]) { // Update the end index of the previous // location to include the current location previous[1] = current[1]; } // If the current location does not overlap with // the previous location else { // Add the current location to the new list newLocations.Add(current); // Update the previous location to be the // last location in the new list previous = newLocations[newLocations.Count - 1]; } } // Return the list of collapsed locations return newLocations; } static string Underscorify( string str, List<List< int > > locations) { int locationsIdx = 0; int stringIdx = 0; bool inBetweenUnderscores = false ; var finalChars = new System.Text.StringBuilder(); int i = 0; while (stringIdx < str.Length && locationsIdx < locations.Count) { if (stringIdx == locations[locationsIdx][i]) { finalChars.Append( "_" ); inBetweenUnderscores = !inBetweenUnderscores; if (!inBetweenUnderscores) { locationsIdx++; } i = i == 1 ? 0 : 1; } finalChars.Append(str[stringIdx]); stringIdx++; } if (locationsIdx < locations.Count) { finalChars.Append( "_" ); } else if (stringIdx < str.Length) { finalChars.Append(str.Substring(stringIdx)); } return finalChars.ToString(); } static void Main( string [] args) { string S1 = "examwill be a examexam" ; string S2 = "exam" ; Console.WriteLine(UnderscorifySubstring(S1, S2)); } } |
_exam_will be a _examexam_
Time Complexity: O(N * M), where N and M is the length of the string S1 and S2 respectively.
Auxiliary Space: O(N), where N is the length of string S1
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!