Given a valid parentheses string s, return the nesting depth of s. The nesting depth is the maximum number of nested parentheses.
Example 1:
Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation:
Digit 8 is inside of 3 nested parentheses in the string.
Example 2:
Input: s = "(1)+((2))+(((3)))"
Output: 3
Explanation:
Digit 3 is inside of 3 nested parentheses in the string.
Example 3:
Input: s = "()(())((()()))"
Output: 3
Constraints:
1 <= s.length <= 100s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.s is a VPS.This approach utilizes a single counter to track the current depth of nesting while iterating through the string. Whenever an open parenthesis '(' is encountered, the counter is incremented, and whenever a closing parenthesis ')' is encountered, the counter is decremented. The maximum value of the counter at any point during the iteration is recorded as the maximum nesting depth.
The code iterates through each character of the string. For each '(', the depth counter is increased and checked against the current maximum depth. For each ')', the depth counter is decreased. The maximum recorded depth is returned as the result.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), as only a few variables are used.
This approach uses a stack to simulate the depth of nested parentheses. Each time an open parenthesis '(' is encountered, it is pushed onto the stack, and for each closing parenthesis ')', an item is popped. The maximum size of the stack during this process reflects the maximum nesting depth.
The C code uses an array as a stack to keep track of open parentheses. The depth is reflected by the top index of the stack, which indicates the number of open parentheses nested relatively.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n). Space Complexity: O(n) due to stack usage.
| Approach | Complexity |
|---|---|
| Using a Simple Counter | Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), as only a few variables are used. |
| Track Depth Using Stack | Time Complexity: O(n). Space Complexity: O(n) due to stack usage. |
maximum nesting depth of the parentheses leetcode | leetcode 1614 | string • Naresh Gupta • 14,055 views views
Watch 9 more video solutions →Practice Maximum Nesting Depth of the Parentheses with our built-in code editor and test cases.
Practice on FleetCode