Given a string S and a list of strings subs[] that stores the substrings of S and all the substrings are present only once, the task is to enclose the substrings of S that exists in subs[] in parentheses. If substrings in subs[] overlap each other or are consecutive then merge them into one set of parentheses.
Examples:
Input: S = “abcdefgh”, subs = {“ef”, “bc”, “g”}
Output: “a(bc)d(efg)h”
Explanation: Substrings “ef” and “g” are consecutive.
So they are enclosed within one set of parentheses.
Substring “bc” is enclosed within one set of parenthesesInput: S = “abcdefgh”, subs = [“abcde”, “bc”]
Output: “(abcde)fgh”
Explanation: Substrings “abcde” and “bc” overlap.
So they are enclosed within one set of parentheses.
Approach: The idea to solve the problem is as follows:
We can find the starting and ending index of each substring of subs[] in the string S. Then they can be considered as separate intervals and we can use the concept of merging overlapping intervals to merge them and enclose them in parentheses.
Follow the below steps to implement the idea:
- Create a list to store the opening and closing positions of each substring of subs[].
- Merge these intervals of opening and closing positions. For that do the following:
- Sort all intervals by opening position in ascending order.
- Starting with the first interval, traverse the sorted intervals and do the following for each interval:
- If the current interval is not the initial interval and it overlaps with the previous interval, merge them together.
- If not, add the current interval to the output interval list.
- Go through the merged interval list and insert the parentheses accordingly into the string S.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function that takes a set of// intervals, merges overlapping and// contiguous intervals and// returns the merged intervalsvector<vector<int> > mergeIntervals(vector<vector<int> >& interval){ // Stores the new indices after // merging vector<vector<int> > mergedInterval; int start = interval[0][0]; int end = interval[0][1]; for (int i = 1; i < interval.size(); i++) { // Intervals merge so update end index if (interval[i][0] <= end || interval[i][0] == end + 1) { end = max(end, interval[i][1]); } else { // Intervals don't merge so // add current interval to // mergedInterval vector<int> al; al.push_back(start); al.push_back(end); mergedInterval.push_back(al); // Update start and end index start = interval[i][0]; end = interval[i][1]; } } // Add last interval to merged interval vector<int> al; al.push_back(start); al.push_back(end); mergedInterval.push_back(al); return mergedInterval;}// Function finds the starting and// ending position of// substring in given input stringvector<int> findSubStringIndex(string subStr, string s){ int i = 0, j = subStr.length(); while (j <= s.length()) { if (s.substr(i, j - i) == subStr) { return { i, j - 1 }; } j++; i++; } return {};}// Function to add parentheses at given indexstring addParentheses(string s, string subs[]){ // Interval stores the opening, // closing position of each // substring in subs vector<vector<int> > interval(subs->size(), vector<int>(2)); // Loop through each substring in // subs and add the opening and // closing positions into intervals for (int i = 0; i < subs->size(); i++) { interval[i] = findSubStringIndex(subs[i], s); } // Sort the intervals according to // opening index position sort(begin(interval), end(interval)); vector<vector<int> > mergedInterval = mergeIntervals(interval); string sb; int pre = 0; // Add the opening and closing // brackets at the positions from // mergedIntervals for (auto& arr : mergedInterval) { sb += s.substr(pre, arr[0] - pre); sb += '('; sb += s.substr(arr[0], arr[1] + 1 - arr[0]); sb += ')'; pre = arr[1] + 1; } sb += s.substr(pre, s.size() - pre); return sb;}// Driver Codeint main(){ string S = "abcdefgh"; string subs[] = { "ef", "bc", "g" }; // Function call cout << addParentheses(S, subs) << "\n"; return 0;}// This code is contributed by Rohit Pradhan |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to add parentheses at given index static String addParentheses(String s, String[] subs) { // Interval stores the opening, // closing position of each // substring in subs int[][] interval = new int[subs.length][2]; // Loop through each substring in // subs and add the opening and // closing positions into intervals for (int i = 0; i < subs.length; i++) { interval[i] = findSubStringIndex(subs[i], s); } // Sort the intervals according to // opening index position Arrays.sort(interval, (a, b) -> a[0] - b[0]); ArrayList<ArrayList<Integer> > mergedInterval = mergeIntervals(interval); StringBuilder sb = new StringBuilder(); int pre = 0; // Add the opening and closing // brackets at the positions from // mergedIntervals for (ArrayList<Integer> arr : mergedInterval) { sb.append(s.substring(pre, arr.get(0))); sb.append("("); sb.append( s.substring(arr.get(0), arr.get(1) + 1)); sb.append(")"); pre = arr.get(1) + 1; } sb.append(s.substring(pre, s.length())); String ans = new String(sb); return ans; } // Function that takes a set of // intervals, merges overlapping and // contiguous intervals and // returns the merged intervals private static ArrayList<ArrayList<Integer> > mergeIntervals(int[][] interval) { // Stores the new indices after // merging ArrayList<ArrayList<Integer> > mergedInterval = new ArrayList<>(); int start = interval[0][0]; int end = interval[0][1]; for (int i = 1; i < interval.length; i++) { // Intervals merge so update end index if (interval[i][0] <= end || interval[i][0] == end + 1) { end = Math.max(end, interval[i][1]); } else { // Intervals don't merge so // add current interval to // mergedInterval ArrayList<Integer> al = new ArrayList<>(); al.add(start); al.add(end); mergedInterval.add(al); // Update start and end index start = interval[i][0]; end = interval[i][1]; } } // Add last interval to merged interval ArrayList<Integer> al = new ArrayList<>(); al.add(start); al.add(end); mergedInterval.add(al); return mergedInterval; } // Function finds the starting and // ending position of // substring in given input string static int[] findSubStringIndex(String subStr, String s) { int i = 0, j = subStr.length(); while (j <= s.length()) { if (s.substring(i, j).equals(subStr)) { return new int[] { i, j - 1 }; } j++; i++; } return null; } // Driver Code public static void main(String[] args) { String S = "abcdefgh"; String[] subs = { "ef", "bc", "g" }; // Function call System.out.println(addParentheses(S, subs)); }} |
Python3
# Python 3 code to implement the approach# Function that takes a set of# intervals, merges overlapping and# contiguous intervals and# returns the merged intervalsdef mergeIntervals(interval): # Stores the new indices after merging mergedInterval = [] start = interval[0][0] end = interval[0][1] for i in range(1, len(interval)): # Intervals merge so update end index if interval[i][0] <= end or interval[i][0] == end+1: end = max(end, interval[i][1]) else: # Intervals don't merge so # add current interval to # mergedInterval al = [] al.append(start) al.append(end) mergedInterval.append(al) # Update start and end index start = interval[i][0] end = interval[i][1] # Add last interval to merged interval al = [] al.append(start) al.append(end) mergedInterval.append(al) return mergedInterval # Function finds the starting and# ending position of# substring in given input stringdef findSubStringIndex(subStr, s): i = 0 j = len(subStr) while(j < len(s)): if s[i:j] == subStr: return [i, j-1] j += 1 i += 1 # Function to add parentheses at given indexdef addParentheses(s, subs): # Interval stores the opening, # closing position of each # substring in subs interval = [0]*len(subs) # Loop through each substring in # subs and add the opening and # closing positions into intervals for i in range(len(subs)): interval[i] = findSubStringIndex(subs[i], s) # Sort the intervals according to # opening index position interval.sort() mergedInterval = mergeIntervals(interval) sb = "" pre = 0 # Add the opening and closing # brackets at the positions from # mergedIntervals for arr in mergedInterval: sb += s[pre:arr[0]] sb += '(' sb += s[arr[0]:arr[1] + 1] sb += ')' pre = arr[1] + 1 sb += s[pre:len(s)] return sb# Driver codeS = "abcdefgh"subs = ['ef', 'bc', 'g']print(addParentheses(S, subs))'''This code is contributed by RAJAT KUMAR...''' |
Javascript
<script>// JavaScript code to implement the approach// Function that takes a set of// intervals, merges overlapping and// contiguous intervals and// returns the merged intervalsfunction mergeIntervals(interval){ // Stores the new indices after // merging let mergedInterval = []; let start = interval[0][0]; let end = interval[0][1]; for (let i = 1; i < interval.length; i++) { // Intervals merge so update end index if (interval[i][0] <= end || interval[i][0] == end + 1) { end = Math.max(end, interval[i][1]); } else { // Intervals don't merge so // add current interval to // mergedInterval let al = []; al.push(start); al.push(end); mergedInterval.push(al); // Update start and end index start = interval[i][0]; end = interval[i][1]; } } // Add last interval to merged interval let al = []; al.push(start); al.push(end); mergedInterval.push(al); return mergedInterval;}// Function finds the starting and// ending position of// substring in given input stringfunction findSubStringIndex(subStr, s){ let i = 0, j = subStr.length; while (j <= s.length) { if (s.substring(i, j) == subStr) { return [ i, j - 1 ]; } j++; i++; } return [];}// Function to add parentheses at given indexfunction addParentheses(s,subs){ // Interval stores the opening, // closing position of each // substring in subs let interval = new Array(subs.length).fill(0).map(()=>new Array(2)); // Loop through each substring in // subs and add the opening and // closing positions into intervals for (let i = 0; i < subs.length; i++) { interval[i] = findSubStringIndex(subs[i], s); } // Sort the intervals according to // opening index position interval.sort((a,b)=>a[0]-b[0]); let mergedInterval = mergeIntervals(interval); let sb = ""; let pre = 0; // Add the opening and closing // brackets at the positions from // mergedIntervals for (let arr of mergedInterval) { sb += s.substring(pre, arr[0]); sb += '('; sb += s.substring(arr[0], arr[1] + 1); sb += ')'; pre = arr[1] + 1; } sb += s.substring(pre, s.length); return sb;}// Driver Codelet S = "abcdefgh";let subs = [ "ef", "bc", "g" ];// Function calldocument.write(addParentheses(S, subs),"</br>");// This code is contributed by shinjanpatra</script> |
C#
// C# code to implement the approachusing System;using System.Collections;using System.Collections.Generic;using System.Linq;class GFG{ // Function to add parentheses at given index static string AddParentheses(string s, string[] subs) { // Interval stores the opening, // closing position of each // substring in subs int[][] interval = new int[subs.Length][]; for (int i = 0; i < subs.Length; i++) { interval[i] = FindSubStringIndex(subs[i], s); } // Sort the intervals according to // opening index position Array.Sort(interval, (a, b) => a[0] - b[0]); ArrayList mergedInterval = MergeIntervals(interval); string ans = ""; int pre = 0; // Add the opening and closing // brackets at the positions from // mergedIntervals foreach (ArrayList arr in mergedInterval) { ans += s.Substring(pre, (int)arr[0] - pre); ans += "("; ans += s.Substring((int)arr[0], (int)arr[1] - (int)arr[0] + 1); ans += ")"; pre = (int)arr[1] + 1; } ans += s.Substring(pre, s.Length - pre); return ans; } // Function that takes a set of // intervals, merges overlapping and // contiguous intervals and // returns the merged intervals private static ArrayList MergeIntervals(int[][] interval) { // Stores the new indices after // merging ArrayList mergedInterval = new ArrayList(); int start = interval[0][0]; int end = interval[0][1]; for (int i = 1; i < interval.Length; i++) { // Intervals merge so update end index if (interval[i][0] <= end || interval[i][0] == end + 1) { end = Math.Max(end, interval[i][1]); } else { // Intervals don't merge so // add current interval to // mergedInterval ArrayList al = new ArrayList(); al.Add(start); al.Add(end); mergedInterval.Add(al); // Update start and end index start = interval[i][0]; end = interval[i][1]; } } // Add last interval to merged interval ArrayList al2 = new ArrayList(); al2.Add(start); al2.Add(end); mergedInterval.Add(al2); return mergedInterval; } // Function finds the starting and // ending position of // substring in given input string static int[] FindSubStringIndex(string subStr, string s) { int i = 0, j = subStr.Length; while (j <= s.Length) { if (s.Substring(i, j - i).Equals(subStr)) { return new int[] { i, j - 1 }; } j++; i++; } return null; } // Driver Code public static void Main(string[] args) { string S = "abcdefgh"; string[] subs = { "ef", "bc", "g" }; // Function call Console.WriteLine(AddParentheses(S, subs)); }}// Contributed by adityashae15 |
Output
a(bc)d(efg)h
Time Complexity: O(N*logN + N*M) where N is the size of subs[] and M is the length of S
Auxiliary Space: O(N)
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!
