Maximum Nesting Depth of the Parentheses in Java

The concept of Maximum Nesting Depth of Parentheses is commonly encountered in string parsing and mathematical expression evaluation. It refers to the deepest level of nested parentheses within a given string.

Given a string containing only the characters '(' and ')' our objective is to determine the maximum depth of nested parentheses. The depth increases when encountering an opening parenthesis '(' and decreases when encountering a closing parenthesis ')'. The highest value attained in this process is the result.

Examples

Example 1:

Input: String s = "((3+2)*((5-1)+2))";

Output: 3

Explanation

There are several sets of nested parentheses in this expression. The maximum nesting depth is at the innermost nesting level within "((5-1)+2)", which has a depth of 3. The depth begins at 0 and rises whenever an opening parenthesis '(' is met. The first parenthesis at position 0 raises the depth to 1, and the second opening parenthesis at position 1 raises to 2.

Continuing a third opening parenthesis at position 7 raises the depth to 3, which is the highest nesting depth in this expression. When closing parentheses ')' are met, the depth is reduced accordingly. The maximum depth recorded during the traversal of the string is 3, which is the final output.

Example 2:

Input: String s = "(4+5)-(6/2)+(7*3)";

Output: 1

Explanation

In this case, the given expression contains multiple pairs of parentheses, but none of them are nested within each other. Every parenthesis set is standalone and has a depth of only 1. While we traverse the string, the depth becomes 1 as we encounter an opening parenthesis '(' and drops back to 0 when we encounter a closing parenthesis ')'.

Because there is no nesting within any parenthesis set, the depth never goes higher than 1. The answer is thus 1.

Example 3:

Input: String s = "((((1+(2))))+((((3+(4*5))))))”;

Output : 6

Explanation

The depth begins at 0 and is incremented each time an opening parenthesis '(' is found. The first parenthesis at index 0 raises the depth to 1, followed by the second one at index 1, raising it to 2, and the third one at index 2, taking it to 3, and the fourth one at index 3, raising it to 4.

The nesting continues with the fifth opening parenthesis at index 4, taking it to a depth of 5. Further along in the expression, another very deeply nested segment "((((3+(4*5)))))" is seen, where a further opening parenthesis at index 14 takes the depth to 6. Continuing with the traversal, each closing parenthesis ')' brings the depth down, but the highest recorded depth is 6, which is the output.

Approach 1: Using Iteration

Algorithm

Step 1: Declare two integer variables, maxDepth to keep a record of the highest depth reached and currentDepth to keep a check on the depth while traversing the string. Initialize both the variables to zero at the start.

Step 2: Loop through every character of the input strings. When an opening parenthesis '(' is encountered, increase currentDepth by one and update maxDepth if currentDepth is higher than the highest depth found so far.

Step 3: If a closing parenthesis ')' is read, then decrement currentDepth by one to indicate the decrease in nesting. As the parentheses are properly formed, currentDepth will never go below zero.

Step 4: Keep iterating over the string until all characters have been scanned and keeping track of counting all opening and closing parentheses correctly.

Step 5: Once traversal is done, then return maxDepth as the result, which is the maximum nesting level found in the input expression.

Step 6: The solution effectively computes the maximum nesting depth in a single pass over the string through a counter-based method without any need for extra data structures.

Implementation

Output:

 
Example 1 - Maximum Depth: 3
Example 2 - Maximum Depth: 1
Example 3 - Maximum Depth: 6   

Complexity Analysis

Time Complexity

The time complexity of this algorithm is O(n) because each character in the string is processed exactly once.

Space Complexity

The space complexity is O(1) since only a few integer variables are used, regardless of the input size.

Approach 2: Using Recursion

Algorithm

Step 1: Begin by declaring a recursive function that goes through each character of the string individually. Keep three variables: the current index to keep track of the position in the string, the current depth to keep a count of open parentheses, and the maximum depth to hold the highest nesting level reached.

Step 2: If the index is at the end of the string, return the highest depth seen so far since there is no further processing. If an opening parenthesis '(' is encountered at the current index and then increment the current depth by one and update the maximum depth if the current depth is higher than the previous maximum.

Step 3: If a closing parenthesis ')' is found, reduce the current depth by one since it indicates the end of a nested section. For any other character that is not a parenthesis, proceed to the next index without modifying the depth values.

Step 4: Proceed recursively until the entire string characters are handled. For each recursive call, modify the depth values as appropriate and make sure that the function visits each character of the input string.

Step 5: After the recursion is finished then return the highest depth ever recorded, as it is the deepest nesting level of the parentheses in the provided expression.

Implementation

Output:

 
Example 1 - Maximum Depth: 3
Example 2 - Maximum Depth: 1
Example 3 - Maximum Depth: 6   

Complexity Analysis

Time Complexity

The time complexity of this approach is O(n) because each character is processed once.

Space Complexity

The space complexity is O(n) due to the recursive call stack, which can grow proportionally to the depth of the input.

Approach 3: Using Stack

Algorithm

Step 1: Initialize an empty stack to keep track of opening parentheses and a variable to hold the maximum depth reached. Iterate over the input string, character by character, and look for opening or closing parentheses.

Step 2: If an opening parenthesis '(' is encountered, push it onto the stack and increment the maximum depth according to the current size of the stack. If a closing parenthesis ')' is encountered, pop an element from the stack as it marks the end of a nested section.

Step 3: Keep processing the string while keeping track of only the valid parentheses and ignoring all the rest of the characters like numbers and operators.

Step 4: The depth grows with every level of nested parentheses and drops as closing parentheses are reached.

Step 5: When the whole string has been processed, the greatest depth reached is returned as the result.

Implementation

Output:

 
Example 1 - Maximum Depth: 3
Example 2 - Maximum Depth: 1
Example 3 - Maximum Depth: 6   

Complexity Analysis

Time Complexity

The time complexity is O(n) because each character in the string is processed exactly once.

Space Complexity

The space complexity is O(n) in the worst case, where the stack stores a large number of nested parentheses, but in most cases, the space usage is significantly lower.