Leetcode 1614: Maximum Nesting Depth of the Parentheses

Category: Easy

Problem

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 a string s, return the nesting depth of s.

https://leetcode.com/problems/maximum-nesting-depth-of-the-parentheses/

Examples:

Example 1

Example 2

Example 3

Example 4

Constraints:

  • 1 <= s.length <= 100
  • s consists of digits 0-9 and characters '+''-''*''/''(', and ')'.
  • It is guaranteed that parentheses expression s is a VPS.

Solution Approach

In this problem, we need to find the maximum depth of the parenthesis. Straightaway we see a lot of information that we are provided with the question which can be very overwhelming. 

The problems like these where there is a lot of information, I try to get the gist of what it requires using the examples as they paint a clearer picture of the problem. There can be a lot of techniques which can be applied to this question but I try to think of an easy solution and what all data we require. 

Most of the people who studied stacks will be impatient to solve this problem using them like its shown in Valid parenthesis problem but here the complications are very minimal as we have only one type of brace and we actually don’t require the other operations or digits. I think the only two symbols which are of utmost importance in this problem is ‘(‘ and ‘)’.

Coming to the solution we take two variables one which will count the depth currently and one which will store the maximum depth value with both being initialised to zero. Now we iterate the string and if we encounter opening curly brace symbol ‘(‘ then we increase the count and if we encounter the closing curly brace we will decrease the count by 1 and also compare with the value with maxCount variable and change it if the present value is greater than the past value of maxCount. Like I said before all the other digits and operators are insignificant. In the end, we return the value in maxCount as the answer.

Solution Code

For more Leetcode explained solutions visit Leetcode Solutions. If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in comment section or contact me via Contact page I will surely respond. Happy Leetcoding

Leave a Comment

Your email address will not be published. Required fields are marked *