1614. Maximum Nesting Depth of the Parentheses

Problem Overview

The string is a valid formula, so every closing parenthesis matches an earlier opening one.

Intuition

The string is a valid formula, so every closing parenthesis matches an earlier opening one. Depth is just how many parentheses are currently open. One counter goes up on each opening parenthesis and down on each closing one, and the answer is the highest value that counter reaches. Digits and operators sit between the parentheses and do not change the depth.

Algorithm

1Start the current depth and the answer at 0.
2Walk each character once.
3On an opening parenthesis, increase the depth and keep it if it is larger than the answer.
4On a closing parenthesis, decrease the depth.
5Skip every other character.
6Return the answer.

Example Walkthrough

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

1.The first parenthesis opens depth 1, and the parenthesis before 2 opens depth 2.
2.The pair around 8 opens one more level, so the depth reaches 3.
3.Each closing parenthesis steps the depth back down.

Output: 3

Common Pitfalls

•The answer is the deepest point, not the number of parenthesis pairs.
•Digits and operators are part of the string and must be ignored.
•A stack of every character uses extra memory. The open count already stores the only value that stack would hold.
•The string is valid, so the depth never goes negative and finishes at 0.

1614.cs

// Approach: A valid string only needs a running open count. Each '(' deepens
// the nest and each ')' closes it. The answer is the highest count seen.
// Letters and operators never change the depth.
// Complexity: O(n) time, O(1) extra space.
public class Solution
{
    public int MaxDepth(string s)
    {
        int ans = 0;
        int opened = 0;

        foreach (char c in s)
        {
            if (c == '(')
                ans = Math.Max(ans, ++opened);
            else if (c == ')')
                --opened;
        }

        return ans;
    }
}

Was this solution helpful?