Maximum Depth of Nested Parenthesis.

Given a string consisting of opening and closing parentheses, find the maximum depth of nested parentheses. The depth of a valid nested parentheses expression is defined as the number of parenthesis pairs that are properly nested. Implement a function that takes a string as input and returns the maximum depth of nested parentheses.

The input string s consists of parentheses characters '(' and ')' only.
The length of s is between 1 and 1000.

Example:

Input: "(A)"

Output: 1

Explanation: The depth of the parentheses is 1.

Input: "((A+B))+(A(B-(C*D)))"

Output: 3

Explanation: The depth of the parentheses is 3.

You might have already guessed that this problem is a standard stack-based problem in which we have to find the maximum depth of the nested parenthesis. In this article, I will explain two different approaches to solving this problem one is of course using stack and another solution is without using any additional data structure.

Maximum Depth of Nested Parenthesis using Stack.

In this approach, we use a stack to track the depth of the parenthesis at any particular moment while traversing the given parenthesis string. We will also keep a variable to keep updating the maximum depth whenever we meet a closing parenthesis.

Algorithm Steps:

Initialize an empty stack to keep track of opening parenthesis.
Create a variable count and initialize it with 0, it will store the maximum depth of nested parenthesis.
Traverse the given input string and follow the below steps:
If the character is opening parenthesis '(' then push it into the stack.
If the character is a closing parenthesis ')' then update the value of the count if it is less than the current stack size. Pop an element from the stack.
Return the count variable as the maximum depth of parenthesis.

Below is the code implementation of the above approach:

C++ Java Python C#

// C++ code to find the maximum depth
// of nested parenthesis 
#include <iostream>
#include<stack>
using namespace std;

int maxDepth(string str) {
    stack<char> st;
    int count = 0;

    for(char c:str) {
        if(c == '(') {
            // insert the opening parenthesis 
            st.push(c);
        }else if(c == ')'){
            // update the max depth 
            if(count < st.size()) {
                count = st.size();
            }
            st.pop();
        }
    }
    return count;
}
int main() {
    string str = "((A+B))+(A(B-(C*D)))";

    int result = maxDepth(str);

    cout<< "Maximum Depth: " <<result <<endl;
    return 0;
}

// Java code implementation to find maximum
// depth of nested parenthesis
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        String str = "((A+B))+(A(B-(C*D)))";

        int result = maxDepth(str);

        System.out.println("Maximum Depth: " + result);
    }

    public static int maxDepth(String str) {
        Stack<Character> st = new Stack<>();
        int count = 0;

        for (char c : str.toCharArray()) {
            // insert the opening parenthesis in stack 
            if (c == '(') {
                st.push(c);
            } else if (c == ')') {
                // update the max depth
                if (count < st.size()) {
                    count = st.size();
                }
                st.pop();
            }
        }

        return count;
    }
}

# Python code to find the max depth of parenthesis
def max_depth(s):
stack = []
max_depth = 0

for char in s:
    if char == '(':
        stack.append(char)
    elif char == ')':
        if len(stack) > max_depth:
            max_depth = len(stack)
        stack.pop()

return max_depth

s = "((A+B))+(A(B-(C*D)))"
result = max_depth(s)
print("Maximum Depth:", result)

// C# code to find max depth of nested parenthesis
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string str = "((A+B))+(A(B-(C*D)))";

        int result = MaxDepth(str);

        Console.WriteLine("Maximum Depth: " + result);
    }

    public static int MaxDepth(string str)
    {
        Stack<char> st = new Stack<char>();
        int count = 0;

        foreach (char c in str)
        {
            if (c == '(')
            {
                st.Push(c);
            }
            else if (c == ')')
            {
                if (count < st.Count)
                {
                    count = st.Count;
                }
                st.Pop();
            }
        }

        return count;
    }
}

Output:

Maximum Depth: 3

Time Complexity: O(n) where n is the size of the given input string.
Space Complexity: O(n) as we are using an extra stack to store open parenthesis.

Maximum Depth of Nested Parenthesis Without Using Stack.

In this approach, we are not using any additional data structure like stack. If we observe the previous solution carefully then we figure out that whenever we meet a close parenthesis we are checking the current depth of the stack so we do not need to store the element in the stack. Instead, we can use a variable that will tell us the current depth, and each time we meet a closing parenthesis we will update the maximum of current and previous depth.

Algorithm steps:

Initialize a variable depth to keep track of the current nesting depth. Initially set to 0.
Initialize a variable ans to store the maximum depth encountered during the iteration. Initially set to 0.
Iterate through the given string and follow the steps below:
If the current character is opening parenthesis then increase the value of depth by 1.
Update ans with the maximum value between its current value and the current depth.
If the current character is a closing parenthesis ')', decrement the depth to indicate the end of nesting.
After iterating through the entire string, return the final maximum depth stored in ans.