String Parentheses : 4April POTD

Day 9/75:

Question: Maximum Nesting Depth of the Parentheses -(Easy)

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

• 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.

Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation: Digit 8 is inside of 3 nested parentheses in the string.
        

Input: s = "(1)+((2))+(((3)))"
Output: 3
        

?Intuition: Count of maximum open braces is required (max depth)

Approach1: Stack

Stack is the first approach which basically comes ,when we see Parentheses.

Simply traverse the string and push the Open Brace '(' into stack ,calculate max size of stack thereby poping when encounters Closing Brace '('

Return maximum size of stack.

Code : (Stack)

Time Complexity: O(n)

Space Complexity : O(n) - Stack is used.

==========================================

Approach 2: Optimized

1. Initialize count to track braces count and res to find max count of open braces.
2. If char == ' ( ' , increment count and update res with max count.
3. When char ==' ) ' , decrement count.
4. Return res, with maximum count of Open Parentheses.

Code:

Time Complexity: O(n)

Space Complexity : O(1) - No extra space is used.

Related Question : Maximum Nesting Depth of Two Valid Parentheses Strings