Maximum Nesting Depth of the Parentheses

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

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