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(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.
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: 3Example 3:
Input: s = “1+(2*3)/(2-1)”
Output: 1Example 4:
Input: s = “1”
Output: 0Constraints:
1 <= s.length <= 100
s consists of digits 0-9 and characters ‘+’, ‘-‘, ‘*’, ‘/’, ‘(‘, and ‘)’.
It is guaranteed that parentheses expression s is a VPS.Hint:
The depth of any character in the VPS is the ( number of left brackets before it ) – ( number of right brackets before it )
Compute the Maximum Nesting Depth of the Parentheses
Similar to most Parentheses string problems. We can use a balance counter to record the current depth. If it is an opening Parentheses, we increment the counter/depth, if it is closing Parentheses, we decrement it accordingly. Then, we just need to get the maximum counter during the process until we reach the end of the valid Parentheses string.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public: int maxDepth(string s) { int ans = 0, bal = 0; for (const auto &n: s) { if (n == '(') { ans = max(ans, ++ bal); } else if (n == ')') { bal --; } } return ans; } }; |
class Solution { public: int maxDepth(string s) { int ans = 0, bal = 0; for (const auto &n: s) { if (n == '(') { ans = max(ans, ++ bal); } else if (n == ')') { bal --; } } return ans; } };
The time complexity of this algorithm is O(N) where N is the number in the valid parentheses string. We are using the constant space i.e. O(1).
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Partition Equal Subset Sum Algorithms using DFS, Top-Down and Bottom-up DP
Next Post: How to Fix the Wired Connection Dropping Momentary Due to Failling to Get a New IP via DHCP?