Insert minimum parentheses to make string balanced

0 0 5 minutes read

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));

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 zambiatek!