LeetCode 1614. Maximum Nesting Depth of the Parentheses Solution in Java, C++, Python & More | Explanation + Code

Description

Given a valid parentheses string s, return the nesting depth of s. The nesting depth is the maximum number of nested parentheses.

 

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

Explanation:

Digit 3 is inside of 3 nested parentheses in the string.

Example 3:

Input: s = "()(())((()()))"

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.

Solutions

Solution 1: Traversal

We use a variable d to record the current depth, initially d = 0.

Traverse the string s. When encountering a left parenthesis, increment the depth d by one and update the answer to be the maximum of the current depth d and the answer. When encountering a right parenthesis, decrement the depth d by one.

Finally, return the answer.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

PythonJavaC++GoTypeScriptJavaScriptC#

class Solution: def maxDepth(self, s: str) -> int: ans = d = 0 for c in s: if c == '(': d += 1 ans = max(ans, d) elif c == ')': d -= 1 return ans(code-box)

class Solution { public int maxDepth(String s) { int ans = 0, d = 0; for (int i = 0; i < s.length(); ++i) { char c = s.charAt(i); if (c == '(') { ans = Math.max(ans, ++d); } else if (c == ')') { --d; } } return ans; } }(code-box)

class Solution { public: int maxDepth(string s) { int ans = 0, d = 0; for (char& c : s) { if (c == '(') { ans = max(ans, ++d); } else if (c == ')') { --d; } } return ans; } };(code-box)

func maxDepth(s string) (ans int) { d := 0 for _, c := range s { if c == '(' { d++ ans = max(ans, d) } else if c == ')' { d-- } } return }(code-box)

function maxDepth(s: string): number { let ans = 0; let d = 0; for (const c of s) { if (c === '(') { ans = Math.max(ans, ++d); } else if (c === ')') { --d; } } return ans; }(code-box)

/** * @param {string} s * @return {number} */ var maxDepth = function (s) { let ans = 0; let d = 0; for (const c of s) { if (c === '(') { ans = Math.max(ans, ++d); } else if (c === ')') { --d; } } return ans; };(code-box)

public class Solution { public int MaxDepth(string s) { int ans = 0, d = 0; foreach(char c in s) { if (c == '(') { ans = Math.Max(ans, ++d); } else if (c == ')') { --d; } } return ans; } }(code-box)