Given a string of digits S. The task is to insert a minimum number of opening and closing parentheses into the string S such that the resulting string is balanced and each digit d must be inside d pairs of matching parentheses.
Examples:
Input: S = 221
Output: ((22)1)
Explanation:
The string ((2))((2))(1) is not valid solutions because it is not of minimum length.Input: S = 3102
Output: (((3))1)0((2))
Approach:
- First, we will insert the required opening parentheses for the first element and store its value in p.
- Then we iterate over the string from 1 to length of string and
- Subtract current element from the previous element (int(S[i-1]) – int(S[i])) and store its value in a variable w.
- If w >= 0 then insert w closing parentheses and update p to (p – w). Otherwise,
- Insert current value minus p (int(S[i]) – p) opening parentheses and update p to equal the current value.
- At the end of the loop, we balance parentheses by inserting the required closing parentheses.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;string ParenthesesNesting(string& S){ // To check first element if 0 or not string out = ""; int p; if (S[0] == '0') { out = "0"; p = 0; } else { int t = (S[0] - '0'); while (t--) { out += '('; } out += S[0]; p = (S[0] - '0'); } // Loop from 1 to length of input_string for (int i = 1; i < S.size(); i++) { int w = (S[i - 1] - '0') - (S[i] - '0'); // To check w is greater than or // equal to zero or not if (w >= 0) { int t = w; while (t--) { out += ')'; } out += S[i]; p = p - w; } else { int t = (S[i] - '0') - p; while (t--) { out += '('; } out += +S[i]; p = int(S[i]); } } int y = count(out.begin(), out.end(), '(') - count(out.begin(), out.end(), ')'); out += ')' * int(y); return (out);}int main(){ string S = "221"; cout << ParenthesesNesting(S); return 0;} |
Java
import java.util.Arrays;public class Gfg { static String ParenthesesNesting(String S) { String out = ""; int p; if (S.charAt(0) == '0') { out = "0"; p = 0; } else { int t = (S.charAt(0) - '0'); while (t-- > 0) { out += '('; } out += S.charAt(0); p = (S.charAt(0) - '0'); } for (int i = 1; i < S.length(); i++) { int w = (S.charAt(i - 1) - '0') - (S.charAt(i) - '0'); if (w >= 0) { int t = w; while (t-- > 0) { out += ')'; } out += S.charAt(i); p = p - w; } else { int t = (S.charAt(i) - '0') - p; while (t-- > 0) { out += '('; } out += S.charAt(i); p = S.charAt(i); } } int y = (int)out.chars() .filter(ch -> ch == '(') .count() - (int)out.chars() .filter(ch -> ch == ')') .count(); while (y-- > 0) { out += ')'; } return out; } public static void main(String[] args) { String S = "221"; System.out.println(ParenthesesNesting(S)); }} |
Python3
# Python 3 implementation to balance# the string# Function to insert matching parenthesesdef ParenthesesNesting(S): # To check first element if 0 or not if S[0] == '0': out = '0' p = 0 else: out = '('*(int(S[0])) + S[0] p = int(S[0]) # Loop from 1 to length of input_string for i in range(1, (len(S))): w = int(S[i - 1]) - int(S[i]) # To check w is greater than or # equal to zero or not if(w >= 0): out = out + ')' * int(w) + S[i] p = p - w else: out = out + '(' * (int(S[i]) - p) + S[i] p = int(S[i]) y = out.count('(') - out.count(')') out += ')' * int(y) return(out)# Driver codeif __name__ == '__main__': string = '221' print(ParenthesesNesting(string)) |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG { static string ParenthesesNesting(string S) { // To check first element if 0 or not string output = ""; int p; if (S[0] == '0') { output = "0"; p = 0; } else { int t = (S[0] - '0'); while (t-->0) { output += '('; } output += S[0]; p = (S[0] - '0'); } // Loop from 1 to length of input_string for (int i = 1; i < S.Length; i++) { int w = (S[i - 1] - '0') - (S[i] - '0'); // To check w is greater than or // equal to zero or not if (w >= 0) { int t = w; while (t-->0) { output += ')'; } output += S[i]; p = p - w; } else { int t = (S[i] - '0') - p; while (t-->0) { output += '('; } output += S[i]; p = S[i]-'0'; } } int y = output.Count(c => c == '(') - output.Count(c => c == ')'); while(y-->0) output+=')'; return (output); } public static void Main() { string S = "221"; Console.Write(ParenthesesNesting(S)); }}// This code is contributed by agrawalpoojaa976. |
Javascript
function ParenthesesNesting( S){ // To check first element if 0 or not let out = ""; let p; if (S[0] == '0') { out = "0"; p = 0; } else { let t = parseInt(S[0]); while (t--) { out += '('; } out += S[0]; p = parseInt(S[0]); } // Loop from 1 to length of input_string for (let i = 1; i < S.length; i++) { let w = parseInt(S[i - 1]) - parseInt(S[i]); // To check w is greater than or // equal to zero or not if (w >= 0) { let t = w; while (t--) { out += ')'; } out += S[i]; p = p - w; } else { let t = parseInt(S[i]) - p; while (t--) { out += '('; } out += +S[i]; p = parseInt(S[i]); } } let c1=0, c2=0; for(let i=0; i<out.length; i++) { if(out[i]=='(') c1++; if(out[i]==')') c2++; } let y = c1-c2; while(y--) out += ')'; return (out);}let S = "221";console.log(ParenthesesNesting(S)); |
Output:
((22)1)
Time Complexity: O(n) where n is the length of the string
Auxiliary Space: O(1)
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!
