712069. Maximum Nesting Depth of the Parentheses
Maximum Nesting Depth of the Parentheses
Slug: maximum-nesting-depth-of-the-parentheses
Difficulty: Easy
Id: 712069
Topic Tags: Strings, Data Structures
Company Tags: None
Summary
Given a string containing only parentheses '(', ')', the task is to find the maximum nesting depth of the parentheses. The nesting depth of a parenthesis is the number of opening parentheses that must be matched before it can be closed.
Detailed Explanation
To solve this problem, we will iterate through the input string and keep track of the current nesting depth. When we encounter an open parenthesis '(', we increment the nesting depth, and when we encounter a close parenthesis ')', we decrement the nesting depth. The maximum nesting depth encountered during the iteration is our answer.
Here's a step-by-step breakdown:
- Initialize the maximum nesting depth to 0.
- Iterate through the input string from left to right.
- When an open parenthesis '(', increment the current nesting depth by 1.
- When a close parenthesis ')', decrement the current nesting depth by 1, but do not allow it to go below 0 (since there are no closing parentheses without matching opening ones).
- Update the maximum nesting depth if the current nesting depth is greater than the previous maximum.
Time complexity: O(n), where n is the length of the input string. Space complexity: O(1), as we only use a constant amount of space to store the maximum nesting depth and the current nesting depth.
Optimized Solutions
Java
public int maxNestingDepth(String s) {
int maxDepth = 0;
int currDepth = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
currDepth++;
maxDepth = Math.max(maxDepth, currDepth);
} else if (c == ')') {
currDepth--;
}
}
return maxDepth;
}