Overview

Given a correctly matched parenthesis sequence, the problem asks to find the maximum nesting depth of the parentheses.

Analysis

Key Insight

The depth of parentheses can be expressed as the number of ( characters that have appeared up to the current position minus the number of ) characters.

For example, looking at ((())) from left to right: - ( → depth 1 - (( → depth 2 - ((( → depth 3 (this is the maximum) - ((() → depth 2 - (()) → depth 1 - ()) → depth 0

In other words, the depth increases by 1 each time ( appears, and decreases by 1 each time ) appears.

Comparison with a Naive Approach

This problem can also be solved using a stack. The method involves pushing ( onto the stack and popping from the stack when ) appears. The maximum stack size becomes the answer.

However, in this problem, we don’t need to remember what was pushed onto the stack (since everything is (), so it’s sufficient to manage only the stack size with an integer variable. This reduces the space complexity from \(O(N)\) to \(O(1)\).

Algorithm

1. Initialize variables current_depth (current depth) and max_depth (maximum depth) to \(0\)
2. Iterate through string \(S\) one character at a time from the beginning
   • If (: increment current_depth by \(1\) and update max_depth
   • If ): decrement current_depth by \(1\)
3. The final max_depth is the answer

Concrete Example

For input (()()):

Position	Character	current_depth	max_depth
0	(	1	1
1	(	2	2
2	)	1	2
3	(	2	2
4	)	1	2
5	)	0	2

The answer is \(2\).

Complexity

• Time complexity: \(O(|S|)\)
  • Only a single scan through the string
• Space complexity: \(O(1)\)
  • Only uses two variables, independent of input size

Implementation Notes

• The update of max_depth must be done immediately after reading (. This is because the moment current_depth increases is when a new depth is reached.

• Since the parenthesis sequence is guaranteed to be correctly matched, there is no need to handle cases where current_depth becomes negative or doesn’t return to \(0\) at the end.

  Source Code

S = input()

max_depth = 0
current_depth = 0

for c in S:
    if c == '(':
        current_depth += 1
        max_depth = max(max_depth, current_depth)
    else:  # c == ')'
        current_depth -= 1

print(max_depth)

---

This editorial was generated by claude4.5opus.