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 parentheses def 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 code if __name__ = = '__main__' : string = '221' print (ParenthesesNesting(string)) |
C#
// C# implementation of the above approach using 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)); |
((22)1)
Time Complexity: O(n) where n is the length of the string
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!