Maximum Nesting Depth of Parentheses

Given a valid parentheses string s, your task is to find the maximum nesting depth of parentheses in the string.

• The nesting depth of a string is the maximum number of parentheses that are open at the same time.
• Only the characters ( and ) affect the nesting depth. Other characters are ignored.

Return 0 if the string is empty or contains no parentheses.

Understanding the Problem

We are given a string that may contain a mix of characters, including parentheses ( and ). Our goal is to determine the maximum nesting depth of parentheses in the string.

But what exactly does "nesting depth" mean? It refers to the number of parentheses that are open at the same time during the reading of the string. Think of it like keeping track of how deep inside layers of parentheses we are.

For example, in the expression ((a + b)), when we reach the innermost a + b, we are two layers deep — that's a nesting depth of 2.

Step-by-Step Solution with Example

Step 1: Initialize two variables

We need to track:

• currentDepth: How many parentheses are currently open.
• maxDepth: The maximum value that currentDepth reaches throughout the string.

Step 2: Traverse the string character by character

Loop through the string. For each character:

• If it's an opening bracket (, we increase currentDepth by 1.
• Update maxDepth if currentDepth exceeds it.
• If it's a closing bracket ), we decrease currentDepth by 1.
• Ignore all other characters.

Step 3: Example Walkthrough

Let’s take the example string: (1+(2*3)+((8)/4))+1

We scan from left to right:

Char (   → currentDepth = 1 → maxDepth = 1  
Char 1   → skip  
Char +   → skip  
Char (   → currentDepth = 2 → maxDepth = 2  
Char 2   → skip  
Char *   → skip  
Char 3   → skip  
Char )   → currentDepth = 1  
Char +   → skip  
Char (   → currentDepth = 2  
Char (   → currentDepth = 3 → maxDepth = 3 ✅  
Char 8   → skip  
Char )   → currentDepth = 2  
Char /   → skip  
Char 4   → skip  
Char )   → currentDepth = 1  
Char )   → currentDepth = 0  
Char +   → skip  
Char 1   → skip

Final maxDepth = 3. So, the maximum nesting is 3.

Edge Cases

• Empty String: No parentheses → nesting depth is 0.
• No parentheses at all: For example, "abc+123" → depth is 0.
• Only one pair: "(x)" → depth is 1.
• Deep nesting: "((((x))))" → depth is 4.
• Invalid or mismatched parentheses: If we assume valid input only, we don’t handle errors. But ideally, if we encounter a closing ) without a matching open (, we should either ignore or throw an error based on problem constraints.

Finally

The beauty of this problem is its simplicity. You don't need a complex data structure like a stack — just a simple counter to track the current level of nesting. It's a classic example of how a linear pass through a string with just a few variables can solve what seems like a tricky problem.

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

1. Initialize two variables: depth = 0 and maxDepth = 0.
2. Loop through each character ch in the string s.
3. If ch == '(', increment depth and update maxDepth if depth > maxDepth.
4. If ch == ')', decrement depth.
5. Return maxDepth at the end.

O(1)

Explanation: Only a few counters are used. No extra data structures like stacks are required.