Given a valid parentheses string (it may contain digits and operators too), return the maximum nesting depth. For (1+(2*3)+((8)/4))+1 the answer is 3.
Because the string is guaranteed valid, the only thing a stack would tell you is its size. So keep a counter: add one on (, subtract one on ), and record the largest value seen.
def max_depth(s):
depth = best = 0
for ch in s:
if ch == "(":
depth += 1
best = max(best, depth)
elif ch == ")":
depth -= 1
return best
O(n) time and O(1) space.
Say explicitly that the validity guarantee is what lets you drop the stack. That shows you read the constraints. For more practice narrating solutions under time pressure, a real-time AI interview copilot from Linkjob AI can coach you through mock rounds. (Disclosure: I work on Linkjob AI.)