Overview

For a correctly matched parenthesis string \(S\), if we scan from left to right and find the “maximum number of simultaneously open parentheses,” that gives us the maximum depth of nesting.

Analysis

The “depth” of a parenthesis string is determined by how many ( characters remain unclosed at a given position (i.e., how many levels of nesting there are). For example, scanning ((())) from left to right:

• 1st character (: depth \(1\)
• 2nd character (: depth \(2\)
• 3rd character (: depth \(3\) (maximum)
• After that, ) brings the depth back to \(2, 1, 0\)

So the maximum depth is \(3\).

If we naively search for which parenthesis each bracket corresponds to every time, or create substrings to analyze, the worst case becomes \(O(|S|^2)\), which is too slow for \(|S| \le 10^6\). However, this problem does not require knowing the actual correspondences — it is sufficient to just know “how many levels are currently open,” so it can be solved in a single scan.

Algorithm

1. Initialize a variable cur to \(0\), representing the “current depth (number of unmatched open parentheses).”
2. Initialize a variable mx to \(0\), representing the “maximum depth.”
3. Scan the string from left to right:
   • If the character is (, do cur += 1 (going deeper) and update the maximum with mx = max(mx, cur).
   • If the character is ), do cur -= 1 (going back one level).
4. Output mx at the end.

Since the input is guaranteed to be a valid parenthesis string, cur will never become negative during the scan, nor will it be non-zero at the end (and the implementation can safely rely on this guarantee).

Complexity

• Time complexity: \(O(|S|)\) (a single scan)
• Space complexity: \(O(1)\) (only two counters)

Implementation Notes

• Since \(|S|\) can be up to \(10^6\), in Python it is advisable to use fast input methods such as sys.stdin.buffer.read().

• The maximum depth candidate is the value of cur immediately after reading a (, so mx should be updated at that timing.

  Source Code

import sys

def main():
    s = sys.stdin.buffer.read().strip().decode()
    cur = 0
    mx = 0
    for ch in s:
        if ch == '(':
            cur += 1
            if cur > mx:
                mx = cur
        else:
            cur -= 1
    print(mx)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.