Original problem

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

Original text

Description

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.

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: 3

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 (PHP 8.2)

Notes
LeetCode #1614
/**
 * @throws \Exception
 */
function getNestingDepthMax(string $input): int
{
    $inputLength = \strlen($input);

    $nestingDepth = 0;
    $nestingDepthMax = 0;
    for ($charIndex = 0; $charIndex < $inputLength; $charIndex++) {
        $char = \substr($input, $charIndex, length: 1);

        if (0 === \strcmp(string1: '(', string2: $char)) {
            $nestingDepth++;
        }

        if ($nestingDepth > $nestingDepthMax) {
            $nestingDepthMax = $nestingDepth;
        }

        if (0 === \strcmp(string1: ')', string2: $char)) {
            $nestingDepth--;

            if ($nestingDepth < 0) {
                throw new \Exception(message: 'Invalid string provided');
            }
        }
    }

    if (0 !== $nestingDepth) {
        throw new \Exception(message: 'Invalid string provided');
    }

    return $nestingDepthMax;
}

Tests

Input stringResultTimeMemory
(1+(2*3)+((8)/4))+1377μs1824B
(1+(2*3)+((8)/(16)))+1369μs2112B
(1)+((2))+(((3)))377μs1824B
031μs80B
()()152μs384B
()(()())261μs768B
A040μs96B
AB046μs192B
A(B)169μs384B
A(((B)()((C()))))561μs1632B
)(\Exception
(()\Exception
OS: Ubuntu WSL2 (5.15.146.1-microsoft-standard-WSL2)
CPU: AMD Ryzen 7 5800X
RAM: 16GB

PHP 8.2.17 (cli) (built: Mar 16 2024 08:41:44) (NTS)
Copyright (c) The PHP Group
Zend Engine v4.2.17, Copyright (c) Zend Technologies
    with Zend OPcache v8.2.17, Copyright (c), by Zend Technologies
    with Xdebug v3.3.1, Copyright (c) 2002-2023, by Derick Rethans

memory_limit => -1
xdebug.mode => profile