Find maximum depth of nested parenthesis in a string

We are given a string having parenthesis like below
“( ((X)) (((Y))) )”
We need to find the maximum depth of balanced parenthesis, like 4 in above example. Since ‘Y’ is surrounded by 4 balanced parenthesis.

If parenthesis are unbalanced then return -1.

Examples :

Input : S = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)";
Output : 4

Input : S = "( p((q)) ((s)t) )";
Output : 3

Input : S = "";
Output : 0

Input : S = "b) (c) ()";
Output : -1 

Input : S = "(b) ((c) ()"
Output : -1

Method 1 (Uses Stack)
A simple solution is to use a stack that keeps track of current open brackets.

1) Create a stack. 
2) Traverse the string, do following for every character
     a) If current character is ‘(’ push it to the stack .
     b) If character is ‘)’, pop an element.
     c) Maintain maximum count during the traversal.

Time Complexity : O(n)
Auxiliary Space : O(n)

Method 2 ( O(1) auxiliary space )
This can also be done without using stack.

1) Take two variables max and current_max, initialize both of them as 0.
2) Traverse the string, do following for every character
    a) If current character is ‘(’, increment current_max and 
       update max value if required.
    b) If character is ‘)’. Check if current_max is positive or
       not (this condition ensure that parenthesis are balanced). 
       If positive that means we previously had a ‘(’ character 
       so decrement current_max without worry. 
       If not positive then the parenthesis are not balanced. 
       Thus return -1. 
3) If current_max is not 0, then return -1 to ensure that the parenthesis
   are balanced. Else return max

Below is the implementation of above algorithm.

C/C++

// A C++ program to find the maximum depth of nested 
// parenthesis in a given expression 
#include <iostream> 
using namespace std; 
  
// function takes a string and returns the 
// maximum depth nested parenthesis 
int maxDepth(string S) 
{ 
    int current_max = 0; // current count 
    int max = 0;    // overall maximum count 
    int n = S.length(); 
  
    // Traverse the input string 
    for (int i = 0; i< n; i++) 
    { 
        if (S[i] == '(') 
        { 
            current_max++; 
  
            // update max if required 
            if (current_max> max) 
                max = current_max; 
        } 
        else if (S[i] == ')') 
        { 
            if (current_max>0) 
                current_max--; 
            else
                return -1; 
        } 
    } 
  
    // finally check for unbalanced string 
    if (current_max != 0) 
        return -1; 
  
    return max; 
} 
  
// Driver program 
int main() 
{ 
    string s = "( ((X)) (((Y))) )"; 
    cout << maxDepth(s); 
    return 0; 
} 

Java

//Java program to find the maximum depth of nested  
// parenthesis in a given expression  
  
class GFG { 
// function takes a string and returns the  
// maximum depth nested parenthesis  
  
    static int maxDepth(String S) { 
        int current_max = 0; // current count  
        int max = 0; // overall maximum count  
        int n = S.length(); 
  
        // Traverse the input string  
        for (int i = 0; i < n; i++) { 
            if (S.charAt(i) == '(') { 
                current_max++; 
  
                // update max if required  
                if (current_max > max) { 
                    max = current_max; 
                } 
            } else if (S.charAt(i) == ')') { 
                if (current_max > 0) { 
                    current_max--; 
                } else { 
                    return -1; 
                } 
            } 
        } 
  
        // finally check for unbalanced string  
        if (current_max != 0) { 
            return -1; 
        } 
  
        return max; 
    } 
  
// Driver program  
    public static void main(String[] args) { 
        String s = "( ((X)) (((Y))) )"; 
        System.out.println(maxDepth(s)); 
    } 
} 

Python

# A Python program to find the maximum depth of nested 
# parenthesis in a given expression 
  
# function takes a string and returns the 
# maximum depth nested parenthesis 
def maxDepth(S): 
    current_max = 0
    max = 0
    n = len(S) 
  
    # Traverse the input string 
    for i in xrange(n): 
        if S[i] == '(': 
            current_max += 1
  
            if current_max > max: 
                max = current_max 
        elif S[i] == ')': 
            if current_max > 0: 
                current_max -= 1
            else: 
                return -1
  
    # finally check for unbalanced string 
    if current_max != 0: 
        return -1
  
    return max
  
# Driver program 
s = "( ((X)) (((Y))) )"
print maxDepth(s) 
  
# This code is contributed by BHAVYA JAIN 

PHP

<?php 
// A PHP program to find the  
// maximum depth of nested  
// parenthesis in a given 
// expression 
  
// function takes a string   
// and returns the maximum  
// depth nested parenthesis 
function maxDepth($S) 
{ 
    // current count 
    $current_max = 0;  
      
    // overall maximum count 
    $max = 0;  
    $n = strlen($S); 
  
    // Traverse the input string 
    for ($i = 0; $i < $n; $i++) 
    { 
        if ($S[$i] == '(') 
        { 
            $current_max++; 
  
            // update max if required 
            if ($current_max> $max) 
                $max = $current_max; 
        } 
          
        else if ($S[$i] == ')') 
        { 
            if ($current_max>0) 
                $current_max--; 
            else
                return -1; 
        } 
    } 
  
    // finally check for 
    // unbalanced string 
    if ($current_max != 0) 
        return -1; 
  
    return $max; 
} 
  
// Driver Code 
$s = "( ((X)) (((Y))) )"; 
echo maxDepth($s); 
  
// This code is contributed by mits 
?> 

Output :

Time Complexity : O(n)
Auxiliary Space : O(1)

Find maximum depth of nested parenthesis in a string

C/C++

Java

Python

PHP

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books