# Maximum Nesting Depth of the Parentheses
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-nesting-depth-of-the-parentheses)
Canonical: https://scaleengineer.com/dsa/problems/maximum-nesting-depth-of-the-parentheses
**Data structures:** String, Stack
**Companies:** [Intel](https://scaleengineer.com/companies/intel)
---
## Problem
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.

# Approaches
## Stack-Based Approach
This approach uses a stack to explicitly track the nesting of parentheses. The depth at any point is determined by the number of elements currently in the stack. While intuitive, it's less space-efficient than the counter-based method.
**Time:** O(N), where N is the length of the string `s`. We iterate through the string once, and stack operations (push, pop, size) take constant time on average. · **Space:** O(D), where D is the maximum nesting depth. In the worst-case scenario, such as a string like `'((...))'`, the stack size can grow up to N/2. Therefore, the space complexity is O(N).
**Pros:** The logic is very clear and directly models the concept of nesting.; It's a standard way to handle parenthesis-related problems.
**Cons:** Requires extra space for the stack, which is not optimal for this specific problem.
### Explanation
We can determine the nesting depth by iterating through the string and using a stack to keep track of open parentheses.

- Initialize a variable `maxDepth` to 0 and an empty stack.
- Traverse each character of the input string `s`.
- If the character is an opening parenthesis `'('`, push it onto the stack. The current depth is now the size of the stack. We update `maxDepth` with the maximum value seen so far (`max(maxDepth, stack.size())`).
- If the character is a closing parenthesis `')'`, it signifies the end of a nested level, so we pop from the stack.
- Other characters (digits, operators) are ignored as they do not affect the nesting structure.
- After the loop finishes, `maxDepth` will contain the maximum nesting depth encountered.

```java
import java.util.Stack;

class Solution {
    public int maxDepth(String s) {
        int maxDepth = 0;
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
                maxDepth = Math.max(maxDepth, stack.size());
            } else if (c == ')') {
                stack.pop();
            }
        }
        return maxDepth;
    }
}
```
### Algorithm
1. Initialize `maxDepth = 0`.
2. Initialize an empty stack `st`.
3. Iterate through each character `c` in the string `s`:
   - If `c` is `'('`:
     - Push `c` onto the stack `st`.
     - Update `maxDepth = Math.max(maxDepth, st.size())`.
   - Else if `c` is `')'`:
     - Pop an element from the stack `st`.
4. Return `maxDepth`.

## Single Pass with a Counter
A more optimized approach involves using a simple counter to track the current depth of nested parentheses. This method avoids the overhead of a stack data structure, resulting in constant space complexity.
**Time:** O(N), where N is the length of the string `s`. We make a single pass through the string. · **Space:** O(1), as we only use a few variables to store the counts, regardless of the input string's size.
**Pros:** Extremely efficient in terms of both time and space.; Simple and easy to understand and implement.
**Cons:** This simplified approach works because the problem guarantees a valid parentheses string. It might not be directly applicable to problems where parenthesis validation is also required.
### Explanation
The problem can be solved efficiently by iterating through the string just once and maintaining a count of the current nesting depth.

- Initialize two integer variables: `currentDepth = 0` to track the current number of open parentheses, and `maxDepth = 0` to store the maximum depth found.
- Iterate through the string character by character.
- When an opening parenthesis `'('` is encountered, we are entering a new level of nesting. We increment `currentDepth` and then update `maxDepth` to be the maximum of its current value and the new `currentDepth`.
- When a closing parenthesis `')'` is found, we are exiting a level, so we decrement `currentDepth`.
- Since the problem guarantees a valid parentheses string (VPS), we don't need to handle cases of mismatched parentheses. The `currentDepth` will naturally return to 0 at the end of the string.
- The final value of `maxDepth` is the answer.

```java
class Solution {
    public int maxDepth(String s) {
        int maxDepth = 0;
        int currentDepth = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                currentDepth++;
                maxDepth = Math.max(maxDepth, currentDepth);
            } else if (c == ')') {
                currentDepth--;
            }
        }
        return maxDepth;
    }
}
```
### Algorithm
1. Initialize `currentDepth = 0` and `maxDepth = 0`.
2. Iterate through each character `c` in the string `s`:
   - If `c` is `'('`:
     - Increment `currentDepth`.
     - Update `maxDepth = Math.max(maxDepth, currentDepth)`.
   - Else if `c` is `')'`:
     - Decrement `currentDepth`.
3. Return `maxDepth`.

# Solutions
### CSharp

```csharp
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;
    }
}
```

### Java

```java
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 ; } }
```

### JavaScript

```javascript
/** * @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;
};

```

### CPP

```cpp
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 ; } };
```

### Python

```python
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
```