Maximum Nesting Depth Of The Parentheses - Leetcode Solution

Problem Statement:

A string is a valid parentheses string (denoted VPS) if it meets one of the following conditions:

It is an empty string "", or a single character not equal to "(" or ")", It can be written as AB (A concatenated with B), where A and B are VPS's, or It can be written as (A), where A is a VPS. We can similarly define the nesting depth depth(S) of any VPS S as follows:

depth("") = 0 depth(C) = 0, where C is a string with a single character not equal to "(" or ")". depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's. depth("(" + A + ")") = 1 + depth(A), where A is a VPS. For example, "", "()()", and "()(()())" are VPS's (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS's.

Given a VPS represented as string s, return the nesting depth of s.

Solution:

The given problem involves calculating the maximum nesting depth of parentheses in the given string s. To solve this problem, we can use a stack data structure. We can start by iterating over the string s character by character.

For each character, we can check if it is an opening parenthesis '('. If it is, then we can push it onto the stack. If it is a closing parenthesis ')', we can pop the top element from the stack. We can keep track of the maximum size of the stack during the iteration, which will give us the maximum nesting depth of the parentheses in the string s.

Let's consider some examples to understand the solution approach more clearly:

Example 1:

Input: s = "(1+(2*3)+((8)/4))+1" Output: 3

In this example, the input string s contains nested parentheses up to depth 3. We can initialize a variable max_depth to 0 and a stack to store the opening parentheses. During the iteration, when we encounter an opening parenthesis '(' we push it onto the stack. When we encounter a closing parenthesis ')' we pop an opening parenthesis from the stack. The current size of the stack will give us the current nesting depth. We update the max_depth variable with the maximum value of the current size of the stack and the previous max_depth value. After iterating over all the characters in the string s, we return the max_depth variable as the answer.

Code:

public int maxDepth(String s) { Stack<Character> stack = new Stack<>(); //stack to store opening parentheses int max_depth = 0; for(char c : s.toCharArray()){ if(c == '('){ stack.push(c); max_depth = Math.max(max_depth, stack.size()); } else if(c == ')'){ stack.pop(); } } return max_depth; }

Time Complexity:

The given solution approach involves iterating over the string s once and performing constant-time operations like push and pop on the stack. Therefore, the time complexity of the solution is O(n), where n is the length of the string s.

Space Complexity:

The given solution approach uses a stack to store opening parentheses. The maximum size of the stack will be equal to the maximum nesting depth of parentheses in the string s. Therefore, the space complexity of the solution is O(m), where m is the maximum nesting depth of the parentheses in the string s.

1