Balanced Tree Span Evaluator 4 — Problem Statement & Solution Guide
Problem Description
You are given a string s consisting of parentheses ( and ). A substring is considered a 'balanced tree span' if it is a valid, non-empty sequence of balanced parentheses. The 'score' of a balanced substring is defined as the maximum nesting depth achieved within that substring. Your task is to compute the total 'Balanced Tree Span Evaluator' score, which is the sum of the scores of all distinct, non-overlapping maximal balanced substrings found in the input string. If the input string contains no balanced substrings, return 0.
A maximal balanced substring is a contiguous segment of the string that is itself a valid balanced parenthesis sequence and cannot be extended to the left or right while remaining balanced. For each such maximal segment, determine its peak nesting depth. The final result is the sum of these peak depths across all maximal segments.
For example, in the string ()(), there is one maximal balanced substring ()() with a peak depth of 1. In the string (()), there is one maximal balanced substring (()) with a peak depth of 2. In the string ()((), the maximal balanced substrings are () (depth 1) and () (depth 1), but wait, ()(() is not fully balanced. Let's refine: We scan for maximal valid balanced substrings. For ()((), the first () is maximal (depth 1). The remaining (() is not balanced. So only one maximal segment. Actually, let's look at ()(()). The whole string is one maximal balanced substring. Its peak depth is 2. The score is 2. If the string is ()(), the whole string is one maximal balanced substring. Its peak depth is 1. The score is 1. If the string is ())(), the maximal balanced substrings are () at index 0 and () at index 3. Each has depth 1. Total score is 1 + 1 = 2.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Balanced Tree Span Evaluator 4"
WHY DOES IT MATTER?
Balanced‑parentheses problems appear in compilers, expression evaluators, and many tree‑like data structures. Mastering the stack + DP pattern lets you count or score all valid sub‑structures in linear time, a skill that scales to real‑world parsing and validation pipelines.
OPTIMIZATION CHALLENGE
The breakthrough is realizing that every balanced substring ending at position i either starts at the matching '(' or can be formed by attaching the current minimal pair to any balanced substring that ends just before that '(' . By storing only the count and cumulative depth of substrings ending at each index, we avoid recomputing depths for overlapping intervals.
REAL-WORLD CONNECTION
Think of a distributed log where each '(' is a request start and ')' is its completion. The nesting depth corresponds to concurrent in‑flight requests. Summing depths over all valid intervals is analogous to measuring total concurrency pressure across the system.
When coding this in an interview, first write the stack logic to get matching indices and depths, then add two one‑line DP updates (cnt[i] and sumDepth[i]). Keep the code modular – a helper that returns depth and previous index – and verify with tiny examples like "()()" and "(())".
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem asks for the sum of the maximum nesting depth of every balanced parentheses substring. A naive solution would enumerate all O(n^2) substrings, validate each with a stack, and compute its depth – clearly infeasible for n up to 10^5 or more. The optimal paradigm combines a single left‑to‑right scan with a stack that stores both the index of each '(' and the depth at which it appears. When a ')' is encountered, the matching '(' is popped, giving us the exact depth of the minimal balanced substring defined by that pair. To extend this insight to longer substrings, we use dynamic programming: for each closing parenthesis we keep two auxiliary arrays – cnt[i] (the number of balanced substrings ending at i) and sumDepth[i] (the cumulative depth of those substrings). If the matching '(' is at position j, the new substrings are the one that starts at j plus every balanced substring that ended just before j. Their depth is the maximum of the current pair’s depth and the depth of the preceding substring, which can be derived from sumDepth[j‑1] and cnt[j‑1]. By updating these arrays in O(1) per character, the total answer is the sum of all sumDepth[i]. This linear‑time, linear‑space solution eliminates the quadratic blow‑up of the brute‑force method while preserving exact depth information for every possible balanced span.
Interview Questions on This Problem
Q1How would you compute the total sum of maximum nesting depths for all balanced parentheses substrings in O(n) time?
Traverse the string once, using a stack to store the index and depth of each '(' . When a ')' is found, pop the matching '(' to obtain the depth d of the minimal balanced substring (j,i). Maintain two DP arrays: cnt[i] = 1 + cnt[j‑1] (if j>0) and sumDepth[i] = d + max(d, depthPrev) summed over all previous substrings, which can be expressed as sumDepth[i] = d + sumDepth[j‑1] + (cnt[j‑1] * (d - depthPrev)) where depthPrev is the maximum depth of substrings ending at j‑1. Accumulate sumDepth[i] into the final answer.
Q2Why does a simple stack‑based validation not suffice to compute the required sum?
A stack alone tells you whether a particular substring is balanced and gives the depth of the current pair, but it does not enumerate all possible balanced substrings that end at a given position. Without DP to propagate counts and depths from earlier substrings, you would miss concatenated balanced spans, leading to an under‑count of the total score.
Q3Can you adapt the algorithm to also return the number of distinct balanced substrings, and how would that affect complexity?
Yes. The same DP array cnt[i] already stores the number of balanced substrings ending at i, so the total number of distinct substrings is the sum of all cnt[i]. The algorithm remains O(n) time and O(n) space because we only add a constant‑time update per character.
Examples
Input
s = "()()"
Output
1
Explanation: The entire string "()()" is a single maximal balanced substring. The nesting depth starts at 0, goes to 1 at the first '(', returns to 0 at the first ')', goes to 1 at the second '(', and returns to 0 at the second ')'. The maximum depth reached is 1. Thus, the score is 1.
Input
s = "(())"
Output
2
Explanation: The entire string "(())" is a single maximal balanced substring. The nesting depth goes 0 -> 1 (first '(') -> 2 (second '(') -> 1 (first ')') -> 0 (second ')'). The maximum depth reached is 2. Thus, the score is 2.
Input
s = "())()"
Output
2
Explanation: We identify maximal balanced substrings. The substring at indices 0-1 is "()", which is balanced with a max depth of 1. The character at index 2 is ')', which is unmatched. The substring at indices 3-4 is "()", which is balanced with a max depth of 1. These are two distinct maximal balanced substrings. The total score is 1 + 1 = 2.
Input
s = "(()())"
Output
2
Explanation: The entire string "(()())" is a single maximal balanced substring. The depth trace is: 0 -> 1 -> 2 -> 1 -> 2 -> 1 -> 0. The maximum depth reached is 2. Thus, the score is 2.
Constraints
- 1 <= s.length <= 10^5
- s consists only of characters '(' and ')'
- The string may not be globally balanced
Optimal Approach & Strategy
Perform a single left‑to‑right pass with a stack that stores each '(' index and its depth, and maintain DP arrays for the count and cumulative depth of balanced substrings ending at each position, updating them in O(1) per character.
Brute Force Approach
Generate every possible substring, check if it is a balanced parentheses sequence with a stack, compute its maximum nesting depth, and add it to the answer.
Verified Code Solutions
/**
* @param {string} s
* @return {number}
*/
var maxDepth = function(s) {
let depth = 0;
let maxDepth = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
depth++;
maxDepth = Math.max(maxDepth, depth);
} else {
depth--;
}
}
return maxDepth;
};class Solution {
public:
int maxDepth(string s) {
int depth = 0;
int maxDepth = 0;
for (char c : s) {
if (c == '(') {
depth++;
maxDepth = max(maxDepth, depth);
} else {
depth--;
}
}
return maxDepth;
}
};class Solution {
public int maxDepth(String s) {
int depth = 0;
int maxDepth = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
depth++;
maxDepth = Math.max(maxDepth, depth);
} else {
depth--;
}
}
return maxDepth;
}
}class Solution:
def maxDepth(self, s: str) -> int:
depth = 0
max_depth = 0
for c in s:
if c == '(':
depth += 1
max_depth = max(max_depth, depth)
else:
depth -= 1
return max_depth/**
* @param {string} s
* @return {number}
*/
var maxDepth = function(s) {
let depth = 0;
let maxDepth = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
depth++;
maxDepth = Math.max(maxDepth, depth);
} else {
depth--;
}
}
return maxDepth;
};Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.