Vultr DocsLatest Content

Maximum Nesting Depth of the Parentheses

Updated on 16 June, 2025
Maximum Nesting Depth of the Parentheses header image

Problem Statement

The task involves analyzing a string s that contains a valid parentheses sequence along with digits and some arithmetic operators. The primary goal is to determine the maximum depth of nested parentheses within the string, which is referred to as the "nesting depth." For instance, a depth of three means that there are three layers of opening and corresponding closing parentheses encapsulating a part of the expression at its deepest point.

Examples

Example 1

Input:

s = "(1+(2*3)+((8)/4))+1"

Output:

3

Explanation:

Digit 8 is inside of 3 nested parentheses in the string.

Example 2

Input:

s = "(1)+((2))+(((3)))"

Output:

3

Explanation:

Digit 3 is inside of 3 nested parentheses in the string.

Example 3

Input:

s = "()(())((()()))"

Output:

3

Constraints

  • 1 <= s.length <= 100
  • s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
  • It is guaranteed that parentheses expression s is a VPS.

Approach and Intuition

To solve this problem, one can leverage a simple counter approach to track the depth of nesting as we traverse through the string. Here’s a step-by-step breakdown:

  1. Initialize a variable max_depth to zero to keep track of the maximum nesting depth observed.
  2. Use another variable, current_depth, to track the current depth as we progress through the string.
  3. Traverse each character of the string:
    • When an '(' is encountered, increase current_depth by one and update max_depth if current_depth exceeds it.
    • When a ')' is encountered, decrease current_depth by one.
  4. Given the constraints and structure of the string, it's assured to be a valid parentheses sequence, which simplifies the problem as no error handling for incorrect sequences is required.

Given this approach, using a single traversal (O(n) time complexity), where n is the length of the string, suffices to determine the maximum depth of nesting. Moreover, the constraints ensure that this solution is efficient and scalable for the input size described. The simple iteration and update methodology provide an intuitive path to solve the problem, capitalizing on the predictable nature of a valid parentheses sequence.

Solutions

  • C++
  • Java
cpp 
class Solution {
public:
    int maxDepth(string s) {
        int maximumDepth = 0;
        int countOpen = 0;
    
        for (char ch : s) {
            if (ch == '(') {
                countOpen++;
            } else if (ch == ')') {
                countOpen--;
            }
                
            maximumDepth = max(maximumDepth, countOpen);
        }
            
        return maximumDepth;
    }
};

The problem "Maximum Nesting Depth of the Parentheses" aims to calculate the deepest level of nested parentheses in a given string. The solution in C++ utilizes a straightforward approach to solve this problem by iterating through the string and maintaining a counter for open parentheses. Here's a concise explanation of how the code tackles the problem:

  • Initialize two integer variables: maximumDepth to track the maximum depth of nested parentheses found, and countOpen to count the current number of open parentheses.
  • Iterate through each character of the string using a for loop.
    • If an open parenthesis '(' is encountered, increment the countOpen.
    • If a close parenthesis ')' is encountered, decrement the countOpen.
    • After updating countOpen for either an open or close parenthesis, update maximumDepth to be the greater value between maximumDepth and countOpen.

The maximum value of countOpen throughout the loop gives the maximum depth of nested parentheses in the string, which is then returned by the function.

Ensure the string contains correctly paired parentheses to achieve accurate results with this code.

java 
class Solution {
    public int findMaxDepth(String str) {
        int depth = 0;
        int count = 0;
    
        for (char ch : str.toCharArray()) {
            if (ch == '(') {
                count++;
            } else if (ch == ')') {
                count--;
            }
            depth = Math.max(depth, count);
        }
    
        return depth;
    }
}

In this Java solution, you determine the maximum nesting depth of the parentheses in a provided string. The method, findMaxDepth, takes a string str as its input and initializes two integer variables, depth and count. Both are set to zero.

  • depth keeps track of the maximum depth encountered.
  • count is used to maintain the current depth level as the string is processed.

The method iterates through every character of the string:

  • If the character is an opening parenthesis (, increment count.
  • If it's a closing parenthesis ), decrement count.

After modifying the count for each character, update depth to be the maximum of the current depth and count. The loop ensures that depth reflects the deepest level of nested parentheses found during the iteration.

The final value of depth is the result and gets returned, representing the maximum nesting depth of the parentheses in the string.

Comments

No comments yet.