Find 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.

#include <stdio.h>

int maxDepth(const char* s) {
    int depth = 0, maxDepth = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(') {
            depth++;
            if (depth > maxDepth)
                maxDepth = depth;
        } else if (s[i] == ')') {
            depth--;
        }
    }
    return maxDepth;
}

int main() {
    const char* input = "(1+(2*3)+((8)/4))+1";
    printf("%d\n", maxDepth(input));  // Output: 3
    return 0;
}

#include <iostream>
#include <string>
using namespace std;

int maxDepth(const string& s) {
    int depth = 0, maxDepth = 0;
    for (char ch : s) {
        if (ch == '(') {
            depth++;
            maxDepth = max(maxDepth, depth);
        } else if (ch == ')') {
            depth--;
        }
    }
    return maxDepth;
}

int main() {
    string input = "(1+(2*3)+((8)/4))+1";
    cout << maxDepth(input) << endl;  // Output: 3
    return 0;
}

def max_depth(s):
    depth = 0
    max_depth = 0
    for ch in s:
        if ch == '(':
            depth += 1               # Increase current depth
            max_depth = max(max_depth, depth)  # Update max if needed
        elif ch == ')':
            depth -= 1               # Decrease depth on closing bracket
    return max_depth

# Sample input
print(max_depth("(1+(2*3)+((8)/4))+1"))  # Output: 3

public class MaxParenthesisDepth {
  public static int maxDepth(String s) {
    int depth = 0, maxDepth = 0;
    for (char ch : s.toCharArray()) {
      if (ch == '(') {
        depth++;                   // Increment depth
        maxDepth = Math.max(maxDepth, depth); // Track max depth
      } else if (ch == ')') {
        depth--;                   // Decrement when closing bracket
      }
    }
    return maxDepth;
  }

  public static void main(String[] args) {
    String input = "(1+(2*3)+((8)/4))+1";
    System.out.println(maxDepth(input));  // Output: 3
  }
}

function maxDepth(s) {
  let depth = 0, maxDepth = 0;
  for (let ch of s) {
    if (ch === '(') {
      depth++;                         // Going deeper
      maxDepth = Math.max(maxDepth, depth);
    } else if (ch === ')') {
      depth--;                         // Coming out
    }
  }
  return maxDepth;
}

console.log(maxDepth("(1+(2*3)+((8)/4))+1")); // Output: 3

package main

import (
    "fmt"
)

func maxDepth(s string) int {
    depth, maxDepth := 0, 0
    for _, ch := range s {
        if ch == '(' {
            depth++
            if depth > maxDepth {
                maxDepth = depth
            }
        } else if ch == ')' {
            depth--
        }
    }
    return maxDepth
}

func main() {
    input := "(1+(2*3)+((8)/4))+1"
    fmt.Println(maxDepth(input)) // Output: 3
}

fn max_depth(s: &str) -> i32 {
    let mut depth = 0;
    let mut max_depth = 0;
    for ch in s.chars() {
        if ch == '(' {
            depth += 1;
            if depth > max_depth {
                max_depth = depth;
            }
        } else if ch == ')' {
            depth -= 1;
        }
    }
    max_depth
}

fn main() {
    let input = "(1+(2*3)+((8)/4))+1";
    println!("{}", max_depth(input)); // Output: 3
}

fun maxDepth(s: String): Int {
    var depth = 0
    var maxDepth = 0
    for (ch in s) {
        if (ch == '(') {
            depth++
            if (depth > maxDepth) {
                maxDepth = depth
            }
        } else if (ch == ')') {
            depth--
        }
    }
    return maxDepth
}

fun main() {
    val input = "(1+(2*3)+((8)/4))+1"
    println(maxDepth(input)) // Output: 3
}

func maxDepth(_ s: String) -> Int {
    var depth = 0
    var maxDepth = 0
    for ch in s {
        if ch == "(" {
            depth += 1
            maxDepth = max(maxDepth, depth)
        } else if ch == ")" {
            depth -= 1
        }
    }
    return maxDepth
}

let input = "(1+(2*3)+((8)/4))+1"
print(maxDepth(input)) // Output: 3

function maxDepth(s: string): number {
  let depth = 0, maxDepth = 0;
  for (let ch of s) {
    if (ch === '(') {
      depth++;
      maxDepth = Math.max(maxDepth, depth);
    } else if (ch === ')') {
      depth--;
    }
  }
  return maxDepth;
}

console.log(maxDepth("(1+(2*3)+((8)/4))+1")); // Output: 3

Time complexity

Space complexity

O(1)

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