Maximum Nesting Depth of the Parentheses — Editorial

Opening the reading…

Intuitiondepth is the current unmatched opening count

At any position in a valid parentheses string, every opening parenthesis that has not yet been closed contributes one level of nesting. Count the opening parentheses seen so far, then subtract the closing parentheses seen so far. The result is the number of currently active layers around the position. Digits and operators do not change that count because they add no parentheses layer.

Whenever you read an opening parenthesis, the current depth increases by one, so that new depth may be the largest seen. Whenever you read a closing parenthesis, one layer ends and the depth decreases by one. The answer is therefore not the final depth, which is zero for a valid string, but the largest value reached during the scan.

Approach

Create depth and maxDepth at zero, because no character has been processed and no nesting exists before the scan begins.

Visit each character from left to right exactly once, because nesting at a position depends only on the parentheses already encountered.

When the character is '(', increment depth, because a new unmatched opening parenthesis creates one additional nesting layer.

After increasing depth, update maxDepth if depth is larger, because the newly opened layer may be the deepest point in the entire string.

When the character is ')', decrement depth, because this closing parenthesis removes one active layer; checking the maximum after this step would miss the depth inside the pair.

Ignore digits and operators, because they occur inside the expression but do not change how many parentheses are currently open.

Return maxDepth, because it stores the largest current depth observed before any closing parenthesis could reduce it.

Complexityone scan and constant working memory

MEASURE	BOUND	WHY
Time	O(n)	Each of the n characters is examined once, with only constant work for each character, so no character is revisited or processed through a nested operation.
Space	O(1) extra	The algorithm stores only two integer counters, regardless of the input shape. The input string and returned integer are not working storage, and even a string with maximum possible nesting does not increase the extra space.

Here n is the length of the input string.

Annotated solutionC++ · iterative counter · one pass

CPPScan the expression, update the maximum immediately after every opening parenthesis, and close one layer for every closing parenthesis.

#include <string>
using namespace std;

class Solution {
public:
    int maxDepth(string s) {
        int depth = 0;
        int maxDepth = 0;

        for (char c : s) {
            if (c == '(') {
                depth++;
                if (depth > maxDepth) {
                    maxDepth = depth;
                }
            } else if (c == ')') {
                depth--;
            }
        }

        return maxDepth;
    }
};

The placement of the maximum update is the key detail. An opening parenthesis creates the depth that exists inside its pair, so you record the new value immediately. The later closing parenthesis only marks the end of that layer. Because the string is guaranteed valid, the counter returns to zero after the scan, but that final value is not the answer.