Overview

Given a valid parenthesis string, find the maximum nesting depth of the parentheses.

Analysis

In this problem, we simply need to scan the string from left to right while tracking the depth of parentheses, and record the maximum depth.

• When ( appears, the depth increases by 1
• When ) appears, the depth decreases by 1

This behaves like a stack, but in practice it is sufficient to just manage the depth as a numeric value. Since it is guaranteed that every ( has a corresponding ), the depth will never become negative.

A naive approach might be to recursively examine the parenthesis depth, but since the string length can be up to \(10^6\), recursion carries the risk of stack overflow. Additionally, if we extract substrings at each step, the time complexity becomes large.

For this problem, a single-pass linear-time algorithm that updates the depth is optimal.

For example, let’s look at the string (()(())):

In this way, by updating the depth for each character, we can ultimately obtain the maximum depth.

Algorithm

1. Maintain a variable depth for the current depth and max_depth for the maximum depth seen so far.
2. Scan the string from left to right:
   • If (, increment depth by 1 and update max_depth (if necessary)
   • If ), decrement depth by 1
3. After the scan is complete, output max_depth

Complexity

• Time complexity: \(O(|S|)\)
• Space complexity: \(O(1)\)

Implementation Notes

• Since each character is processed only once, this is very efficient

• Using .strip() to remove leading and trailing whitespace from the input string is a safe practice

• It is sufficient to check max_depth only when encountering ( (since ) only decreases the depth, the maximum value is never updated then)

  Source Code

s = input().strip()

depth = 0
max_depth = 0

for char in s:
    if char == '(':
        depth += 1
        max_depth = max(max_depth, depth)
    elif char == ')':
        depth -= 1

print(max_depth)

This editorial was generated by qwen3-coder-480b.