1614. Maximum Nesting Depth of the Parentheses
Problem Description
The problem defines a valid parentheses string (VPS) with specific rules:
- It can be an empty string
""
, or any single character that is not"("
or")"
. - A string can be considered a VPS if it is the concatenation of two VPS's, denoted as
AB
. - A string is also a VPS if it is of the form
(A)
, whereA
is itself a VPS.
Beyond this, the problem introduces the concept of nesting depth. Nesting depth is the maximum level of nested parentheses within any VPS. It's defined as follows:
depth("") = 0
, for an empty string.depth(C) = 0
, whereC
is any single character other than parentheses.depth(A + B)
is the maximum depth between two VPS'sA
andB
.depth("(" + A + ")")
is the depth ofA
plus one, accounting for the additional level of nesting created by surroundingA
with parentheses.
The task is to calculate and return the nesting depth of a given string s
, which is guaranteed to be a VPS.
Intuition
The solution to determining the nesting depth of a string involves keeping track of the current level of parenthetical depth while iterating through the string character by character. Whenever an opening parenthesis "("
is encountered, we increase the depth, and when a closing parenthesis ")"
is encountered, we decrease the depth.
The intuition behind the solution is as follows:
- A depth tracker variable
d
is initialized to zero. - An answer variable
ans
is also initialized to zero to keep track of the maximum depth encountered. - As we iterate over each character
c
of the strings
:- If
c
is an opening parenthesis(
, we increase thed
count to indicate that we are going a level deeper. - We update the
ans
variable with the maximum between the currentans
and the updated depthd
. - If
c
is a closing parenthesis)
, we decrease thed
count to indicate that we are coming out of a depth level.
- If
- The
ans
will contain the maximum depth achieved throughout the iteration and is returned as the result.
This approach is efficient because it operates in linear time, making a single pass through the string, and requires only a constant amount of extra space.
Learn more about Stack patterns.
Solution Approach
The Reference Solution Approach makes use of a simple yet effective algorithm to find the nesting depth of a valid parentheses string. This approach does not require complex data structures or patterns but relies on basic variables to track the progress. The implementation steps are as follows:
- Initialize two integer variables:
ans
andd
to zero.ans
will hold our final result, the maximum depth of nesting, andd
will keep track of the current depth while iterating through the string. - Iterate over each character
c
in the input strings
.- When
c
is an opening parenthesis(
: a. Increase the depthd
by 1 because we've entered a new layer of nesting. b. Update the answerans
with the greater ofans
ord
. This step ensures thatans
always contains the maximum depth observed so far. - When
c
is a closing parenthesis)
: a. Decrease the depthd
by 1 because we've exited a layer of nesting.
- When
Here's a more detailed breakdown of the algorithm using the provided Python code:
def maxDepth(self, s: str) -> int:
defines a methodmaxDepth
that takes a strings
as an input and returns an integer representing the maximum depth.ans = d = 0
sets up our variables:ans
to track the maximum depth andd
to track the current depth.for c in s:
starts a loop over each character in the string.if c == '(':
checks if the current character is an opening parenthesis.d += 1
increments the current depth because an opening parenthesis indicates deeper nesting.ans = max(ans, d)
updates the maximum depth found so far.elif c == ')':
checks if the current character is a closing parenthesis.d -= 1
decrements the current depth because a closing parenthesis indicates that we are stepping out of a level of nesting.return ans
returns the highest depth of nesting that was recorded during the iteration through the string.
By maintaining a count of the current depth level with each parenthesis encountered and recording the maximum depth along the way, the algorithm effectively computes the nesting depth of the valid parentheses string with a time complexity of O(n) and a space complexity of O(1), where n is the length of the string s
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Consider the string s = "(ab((cd)e))"
. Our goal is to determine the maximum nesting depth of this valid parentheses string.
- We start with
ans = 0
andd = 0
. These will keep track of the maximum depth and the current depth, respectively. - Begin iterating over each character in
s
. - First character:
(
:- Current depth
d
is increased:d = 1
. - Update
ans
:ans = max(0, 1) = 1
.
- Current depth
- Next characters:
ab
, there are no parentheses, sod
andans
remain unchanged. - Next character:
(
:- Current depth
d
is increased:d = 2
. - Update
ans
:ans = max(1, 2) = 2
.
- Current depth
- Next characters:
cd
, there are no parentheses, sod
andans
remain unchanged. - Next character:
)
:- Current depth
d
is decreased:d = 1
.
- Current depth
- Next character:
e
, still no parentheses, sod
andans
remain unchanged. - Next character:
)
:- Current depth
d
is decreased:d = 0
. - The string ends here, and
ans
holds the maximum depth encountered, which is2
.
- Current depth
At the end of this process, the maximum depth ans
is 2
, which is the correct nesting depth of the example string s
. Throughout this iterative process, we have updated ans
whenever a greater depth was achieved and correctly maintained the current depth by incrementing and decrementing d
at the opening and closing parentheses, respectively. The linear scan allowed us to calculate the nesting depth in a single pass, fulfilling the efficient performance as outlined in the solution approach.
Solution Implementation
1class Solution:
2 def maxDepth(self, s: str) -> int:
3 # Initialize variables to store the current depth and maximum depth
4 max_depth = current_depth = 0
5
6 # Iterate through each character in the string
7 for char in s:
8 if char == '(': # If the character is an opening bracket
9 current_depth += 1 # Increase the current depth by 1
10 max_depth = max(max_depth, current_depth) # Update the max depth if needed
11 elif char == ')': # If the character is a closing bracket
12 current_depth -= 1 # Decrease the current depth by 1
13
14 # Return the maximum depth encountered
15 return max_depth
16
1class Solution {
2 public int maxDepth(String s) {
3 int maxDepth = 0; // This will store the maximum depth of the parentheses
4 int currentDepth = 0; // This will keep track of the current depth
5
6 // Iterating over each character in the string
7 for (int i = 0; i < s.length(); ++i) {
8 char c = s.charAt(i); // Get the current character from the string
9
10 if (c == '(') {
11 // If the character is an opening parenthesis, we increase the current depth
12 currentDepth++;
13
14 // Update the maximum depth if the current depth is greater than the maxDepth observed so far
15 maxDepth = Math.max(maxDepth, currentDepth);
16 } else if (c == ')') {
17 // If the character is a closing parenthesis, we decrease the current depth
18 currentDepth--;
19 }
20 // We ignore all other characters
21 }
22
23 // Returning the maximum depth of nesting of the parentheses encountered in the string
24 return maxDepth;
25 }
26}
27
1#include <algorithm> // For using the max function
2#include <string> // For using the string type
3
4class Solution {
5public:
6 // Function to find the maximum depth of parentheses in a given string `s`.
7 int maxDepth(string s) {
8 int maxDepth = 0; // To store the maximum depth encountered
9 int currentDepth = 0; // To track the current depth of open parentheses
10
11 // Iterate through each character in the string
12 for (char& c : s) {
13 if (c == '(') {
14 // Increment the current depth when an opening parenthesis is encountered
15 currentDepth++;
16 // Update the maximum depth encountered so far
17 maxDepth = std::max(maxDepth, currentDepth);
18 } else if (c == ')') {
19 // Decrement the current depth when a closing parenthesis is encountered
20 currentDepth--;
21 }
22 // No action on other characters
23 }
24 // Return the maximum depth of opened parentheses
25 return maxDepth;
26 }
27};
28
1// Function to find the maximum nesting depth of parentheses in a given string.
2function maxDepth(s: string): number {
3 let maxDepth = 0; // This will keep track of the maximum depth encountered
4 let currentDepth = 0; // This will keep track of the current depth
5
6 // Iterate over each character in the input string
7 for (const char of s) {
8 // If the character is an opening parenthesis, increase the current depth
9 if (char === '(') {
10 currentDepth++;
11 // Update the maximum depth if the current depth exceeds it
12 maxDepth = Math.max(maxDepth, currentDepth);
13 } else if (char === ')') {
14 // If the character is a closing parenthesis, decrease the current depth
15 currentDepth--;
16 }
17 // We ignore all other characters
18 }
19
20 return maxDepth; // Return the maximum depth encountered
21}
22
Time and Space Complexity
Time Complexity
The time complexity of the code is a function of the number of characters in the input string, s
. The code consists of a single for
loop that goes through each character of s
exactly once, performing O(1)
operations for each character - increasing or decreasing the depth d
and updating the maximum depth ans
. Therefore, the time complexity is O(n)
, where n
is the length of the input string s
.
Space Complexity
The space complexity of the code is O(1)
. This is because the code uses a fixed number of integer variables ans
and d
, regardless of the input size. No additional structures that grow with input size are used, which means the space used by the algorithm does not depend on the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!