Maximum Nesting Depth of the Parentheses
EasyPrompt
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 <= 100sconsists of digits0-9and characters'+','-','*','/','(', and')'.- It is guaranteed that parentheses expression
sis a VPS.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a stack to explicitly track the nesting of parentheses. The depth at any point is determined by the number of elements currently in the stack. While intuitive, it's less space-efficient than the counter-based method.
Algorithm
- Initialize
maxDepth = 0. - Initialize an empty stack
st. - Iterate through each character
cin the strings:- If
cis'(':- Push
conto the stackst. - Update
maxDepth = Math.max(maxDepth, st.size()).
- Push
- Else if
cis')':- Pop an element from the stack
st.
- Pop an element from the stack
- If
- Return
maxDepth.
Walkthrough
We can determine the nesting depth by iterating through the string and using a stack to keep track of open parentheses.
- Initialize a variable
maxDepthto 0 and an empty stack. - Traverse each character of the input string
s. - If the character is an opening parenthesis
'(', push it onto the stack. The current depth is now the size of the stack. We updatemaxDepthwith the maximum value seen so far (max(maxDepth, stack.size())). - If the character is a closing parenthesis
')', it signifies the end of a nested level, so we pop from the stack. - Other characters (digits, operators) are ignored as they do not affect the nesting structure.
- After the loop finishes,
maxDepthwill contain the maximum nesting depth encountered.
import java.util.Stack; class Solution { public int maxDepth(String s) { int maxDepth = 0; Stack<Character> stack = new Stack<>(); for (char c : s.toCharArray()) { if (c == '(') { stack.push(c); maxDepth = Math.max(maxDepth, stack.size()); } else if (c == ')') { stack.pop(); } } return maxDepth; }}Complexity
Time
O(N), where N is the length of the string `s`. We iterate through the string once, and stack operations (push, pop, size) take constant time on average.
Space
O(D), where D is the maximum nesting depth. In the worst-case scenario, such as a string like `'((...))'`, the stack size can grow up to N/2. Therefore, the space complexity is O(N).
Trade-offs
Pros
The logic is very clear and directly models the concept of nesting.
It's a standard way to handle parenthesis-related problems.
Cons
Requires extra space for the stack, which is not optimal for this specific problem.
A more optimized approach involves using a simple counter to track the current depth of nested parentheses. This method avoids the overhead of a stack data structure, resulting in constant space complexity.
Algorithm
- Initialize
currentDepth = 0andmaxDepth = 0. - Iterate through each character
cin the strings:- If
cis'(':- Increment
currentDepth. - Update
maxDepth = Math.max(maxDepth, currentDepth).
- Increment
- Else if
cis')':- Decrement
currentDepth.
- Decrement
- If
- Return
maxDepth.
Walkthrough
The problem can be solved efficiently by iterating through the string just once and maintaining a count of the current nesting depth.
- Initialize two integer variables:
currentDepth = 0to track the current number of open parentheses, andmaxDepth = 0to store the maximum depth found. - Iterate through the string character by character.
- When an opening parenthesis
'('is encountered, we are entering a new level of nesting. We incrementcurrentDepthand then updatemaxDepthto be the maximum of its current value and the newcurrentDepth. - When a closing parenthesis
')'is found, we are exiting a level, so we decrementcurrentDepth. - Since the problem guarantees a valid parentheses string (VPS), we don't need to handle cases of mismatched parentheses. The
currentDepthwill naturally return to 0 at the end of the string. - The final value of
maxDepthis the answer.
class Solution { public int maxDepth(String s) { int maxDepth = 0; int currentDepth = 0; for (char c : s.toCharArray()) { if (c == '(') { currentDepth++; maxDepth = Math.max(maxDepth, currentDepth); } else if (c == ')') { currentDepth--; } } return maxDepth; }}Complexity
Time
O(N), where N is the length of the string `s`. We make a single pass through the string.
Space
O(1), as we only use a few variables to store the counts, regardless of the input string's size.
Trade-offs
Pros
Extremely efficient in terms of both time and space.
Simple and easy to understand and implement.
Cons
This simplified approach works because the problem guarantees a valid parentheses string. It might not be directly applicable to problems where parenthesis validation is also required.
Solutions
Solution
public class Solution { public int MaxDepth(string s) { int ans = 0, d = 0; foreach(char c in s) { if (c == '(') { ans = Math.Max(ans, ++d); } else if (c == ')') { --d; } } return ans; }}class Solution { public int maxDepth ( String s ) { int ans = 0 , d = 0 ; for ( int i = 0 ; i < s . length (); ++ i ) { char c = s . charAt ( i ); if ( c == '(' ) { ans = Math . max ( ans , ++ d ); } else if ( c == ')' ) { -- d ; } } return ans ; } }/** * @param {string} s * @return {number} */ var maxDepth = function (s) { let ans = 0; let d = 0; for (const c of s) { if (c === " ( ") { ans = Math.max(ans, ++d); } else if (c === " ) ") { --d; } } return ans;};class Solution { public: int maxDepth ( string s ) { int ans = 0 , d = 0 ; for ( char & c : s ) { if ( c == '(' ) { ans = max ( ans , ++ d ); } else if ( c == ')' ) { -- d ; } } return ans ; } };class Solution : def maxDepth ( self , s : str ) -> int : ans = d = 0 for c in s : if c == '(' : d += 1 ans = max ( ans , d ) elif c == ')' : d -= 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.