Code Implementation

class Solution:
    def maxDepth(self, s: str) -> int:
        max_depth = 0
        current_depth = 0
        for char in s:
            if char == '(':
                current_depth += 1
                max_depth = max(max_depth, current_depth)
            elif char == ')':
                current_depth -= 1
        return max_depth
      

class Solution {
public:
    int maxDepth(string s) {
        int max_depth = 0, current_depth = 0;
        for (char c : s) {
            if (c == '(') {
                current_depth++;
                max_depth = max(max_depth, current_depth);
            } else if (c == ')') {
                current_depth--;
            }
        }
        return max_depth;
    }
};
      

class Solution {
    public int maxDepth(String s) {
        int maxDepth = 0, currentDepth = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                currentDepth++;
                maxDepth = Math.max(maxDepth, currentDepth);
            } else if (c == ')') {
                currentDepth--;
            }
        }
        return maxDepth;
    }
}
      

var maxDepth = function(s) {
    let maxDepth = 0, currentDepth = 0;
    for (let char of s) {
        if (char === '(') {
            currentDepth++;
            maxDepth = Math.max(maxDepth, currentDepth);
        } else if (char === ')') {
            currentDepth--;
        }
    }
    return maxDepth;
};
      

Problem Description

Given a string s consisting of digits, operators, and parentheses, you are asked to determine the maximum nesting depth of the parentheses in s. The nesting depth is defined as the maximum number of parentheses that are open at any point in the string.

For example, in the string "(1+(2*3)+((8)/4))+1", the maximum nesting depth is 3 because at one point there are three open parentheses before any are closed.

Key constraints:

• The string s is a valid parentheses string (VPS), meaning all open parentheses have a matching closing parenthesis and are properly nested.
• You only need to return the maximum depth; you do not need to return the actual substring or indices.

Thought Process

The core of this problem is to track how deeply nested the parentheses are as we read through the string. At each character, if we see an open parenthesis '(', we know we are going one level deeper. If we see a close parenthesis ')', we move one level up (out of a nested level).

The simplest approach is to scan the string from left to right, keeping a counter for the current nesting level. Each time we see an open parenthesis, we increment the counter; each time we see a close parenthesis, we decrement it. We keep track of the maximum value this counter reaches, which will be our answer.

A brute-force approach might try to check every possible substring, but that's unnecessary since the nesting depth is determined by the sequence of open and close parentheses, not by their specific positions or contents. Recognizing this allows us to optimize to a single pass with constant space.

Solution Approach

We can solve this problem efficiently in one pass through the string using a simple counter. Here’s how:

• Initialize two variables: current_depth (to track the current level of nesting) and max_depth (to record the maximum depth seen so far).
• Iterate through each character in the string s:
  • If the character is '(', increment current_depth by 1. Then, update max_depth if current_depth is greater than max_depth.
  • If the character is ')', decrement current_depth by 1.
  • Ignore any other characters (digits, operators, etc.).
• After the loop, max_depth will contain the answer.

This approach is efficient because:

• We only need to scan the string once (O(n) time).
• We use only a couple of integer variables (O(1) space).
• We never need to store the actual parentheses or their positions.

Example Walkthrough

Let's use the input s = "(1+(2*3)+((8)/4))+1".

1. We start with current_depth = 0, max_depth = 0.
2. First character is '(': current_depth = 1, max_depth = 1.
3. We see some digits and operators, which we skip.
4. Next '(': current_depth = 2, max_depth = 2.
5. Next '(': current_depth = 3, max_depth = 3.
6. Next ')': current_depth = 2.
7. Continue, closing more parentheses, until current_depth returns to 0.
8. At every step, max_depth always holds the highest value current_depth reached, which is 3.

The function returns 3, which is the correct answer.

Time and Space Complexity

Brute-force approach:

• If we tried to check every substring for valid parentheses and count their depth, it would be O(n²) or worse, since there are O(n²) substrings in a string of length n.

• Time Complexity: O(n), where n is the length of the string. We only scan the string once.
• Space Complexity: O(1), since we only use two integer variables regardless of input size.

This makes the optimized approach highly efficient for even very large strings.

Summary

To solve the Maximum Nesting Depth of Parentheses problem, we track the current depth as we scan the string and record the maximum value reached. This elegant approach leverages the fact that parentheses are properly nested and does not require extra data structures or checking substrings. The result is a simple, fast, and space-efficient solution that works for any valid input.