Maximum Nesting Depth of the Parentheses - LeetCode Daily Challenge

Problem Statement

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

Example 2

Input: "(1)+((2))+(((3)))"
Output: 3

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public int maxDepth(String s) {
        int openBrackets = 0, nestingDepth = 0;

        for(char ch : s.toCharArray()) {
            if(ch == '(') {
                openBrackets += 1;
            } else if(ch == ')') {
                openBrackets -= 1;
            }

            nestingDepth = Math.max(nestingDepth, openBrackets);
        }

        return nestingDepth;
    }
}

C++ Code

class Solution {
public:
    int maxDepth(string s) {
        int openBrackets = 0, nestingDepth = 0;

        for(char ch : s) {
            if(ch == '(') {
                openBrackets += 1;
            } else if(ch == ')') {
                openBrackets -= 1;
            }

            nestingDepth = max(nestingDepth, openBrackets);
        }

        return nestingDepth;
    }
};

Python Code

class Solution:
    def maxDepth(self, s: str) -> int:
        open_brackets = 0
        nesting_depth = 0

        for ch in s:
            if ch == '(':
                open_brackets += 1
            elif ch == ')':
                open_brackets -= 1

            nesting_depth = max(nesting_depth, open_brackets)

        return nesting_depth

Javascript Code

/**
 * @param {string} s
 * @return {number}
 */
var maxDepth = function(s) {
    let openBrackets = 0;
    let nestingDepth = 0;

    for (const ch of s) {
        if (ch === '(') {
            openBrackets += 1;
        } else if (ch === ')') {
            openBrackets -= 1;
        }

        nestingDepth = Math.max(nestingDepth, openBrackets);
    }

    return nestingDepth;
};

Go Code

func maxDepth(s string) int {
    openBrackets := 0
    nestingDepth := 0

    for _, ch := range s {
        if ch == '(' {
            openBrackets += 1
        } else if ch == ')' {
            openBrackets -= 1
        }

        if nestingDepth < openBrackets {
            nestingDepth = openBrackets
        }
    }

    return nestingDepth
}

Time Complexity: O(n)
Space Complexity: O(1)