Practice/Meta/Leetcode 1614. Maximum Nesting Depth of the Parentheses

Leetcode 1614. Maximum Nesting Depth of the Parentheses

CodingOptional

Problem

You are given a string that represents a valid expression containing parentheses along with other characters such as letters, digits, and operators. Your task is to determine the maximum nesting depth of the parentheses in this string.

The nesting depth at any point is defined as the number of opening parentheses that have been encountered but not yet closed. The maximum nesting depth is the highest value this count reaches while scanning through the string from left to right.

For example, in the string "(1+(2*3)+((8)/4))+1", when we reach the innermost part ((8)/4), we have three unclosed opening parentheses, making the maximum depth 3.

Requirements

1. Process the input string from left to right
2. Track the current depth by counting open parentheses
3. Return the maximum depth reached at any point
4. Handle strings that may contain no parentheses (return 0)
5. Assume the input string always contains valid, properly matched parentheses

Constraints

• 1 ≤ length of s ≤ 1000
• The string contains only printable ASCII characters
• All parentheses in the string are properly balanced and matched
• Time complexity should be O(n) where n is the length of the string
• Space complexity should be O(1)

Examples

Example 1:

Input: s = "(1+(2*3)+((8)/4))+1" Output: 3 Explanation: The maximum nesting occurs at "((8)/4)" where there are 3 levels of nested parentheses.

Example 2:

Input: s = "(1)+((2))+(((3)))" Output: 3 Explanation: The substring "(((3)))" has the maximum depth of 3.

Example 3:

Input: s = "()(())" Output: 2 Explanation: The second group "(())" has depth 2, which is the maximum.

Example 4:

Input: s = "abc123" Output: 0 Explanation: No parentheses exist in the string, so the depth is 0.