Overview

Given a valid parenthesis string, the problem asks you to find the depth of the most deeply nested part of its nesting structure.

Analysis

To calculate the depth of parentheses, we need to keep track of “how many unclosed parentheses there currently are.”

Specifically, when scanning the string from left to right, the behavior is as follows: - ( (opening parenthesis) appears: A new nesting layer begins, so the current depth increases by \(1\). - ) (closing parenthesis) appears: The current nesting layer ends, so the current depth decreases by \(1\).

For example, for the string (()()), the depth changes as follows: 1. ( comes: depth \(1\) 2. ( comes: depth \(2\) 3. ) comes: depth \(1\) 4. ( comes: depth \(2\) 5. ) comes: depth \(1\) 6. ) comes: depth \(0\)

Among these changes, the value at the moment the depth reaches its maximum (which is \(2\) in this example) is the desired “maximum depth.”

Algorithm

1. Initialize a variable max_depth to record the maximum depth and a variable current_depth representing the current depth, both to \(0\).
2. Examine each character of string \(S\) one by one from the beginning.
   • If the character is (: Increase current_depth by \(1\).
   • Then, if current_depth is greater than max_depth, update max_depth.
   • If the character is ): Decrease current_depth by \(1\).
3. After examining all characters to the end of the string, output max_depth.

Complexity

• Time complexity: \(O(|S|)\)
  • Since we scan the string of length \(|S|\) in a single loop, the processing completes in linear time.
• Space complexity: \(O(|S|)\)
  • Memory is needed to store the input string.

Implementation Notes

• Fast I/O: Since the constraint on the string length is as large as \(|S| \leq 10^6\), in Python, using sys.stdin.readline() instead of input() can reduce execution time.

• Incremental updates: Updating max_depth only right after ( appears is sufficient. This is because the depth only increases at the moment ( is encountered.

  Source Code

import sys

def solve():
    # 入力を標準入力から読み込む
    s = sys.stdin.readline().strip()
    
    max_depth = 0
    current_depth = 0
    
    # 文字列を1文字ずつ走査
    for char in s:
        if char == '(':
            # 開き括弧が来たら深さを増やす
            current_depth += 1
            # 最大深さを更新
            if current_depth > max_depth:
                max_depth = current_depth
        else:
            # 閉じ括弧が来たら深さを減らす
            current_depth -= 1
            
    # 結果を出力
    print(max_depth)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.