algoadvance

Leetcode 1614. Maximum Nesting Depth of the Parentheses

Problem Statement

Given a valid parentheses string s (a string consisting of ( and ) only), we need to compute the maximum depth of valid nested parentheses.

Example:

• Input: s = “(1+(2*3)+((8)/4))+1”
• Output: 3

Clarifying Questions

1. Q: Will the input string always be valid?
   • A: Yes, the input string is guaranteed to be valid.
2. Q: Are there any constraints on the length of the string?
   • A: Typically, constraints are not explicitly given in the problem statement, but you can assume the string could be as long as the typical constraints for a LeetCode problem, up to 10^4 characters.

Strategy

To find the maximum depth of nested parentheses:

1. Traverse the string from left to right.
2. Initialize a counter to keep track of the current depth.
3. Every time you encounter an opening parenthesis (, increase the depth counter.
4. Every time you encounter a closing parenthesis ), decrease the depth counter.
5. Keep a record of the maximum depth encountered during the traversal.
6. Return the maximum depth as the result.

Code

#include <string>
#include <algorithm>

class Solution {
public:
    int maxDepth(std::string s) {
        int current_depth = 0;
        int max_depth = 0;

        for (char ch : s) {
            if (ch == '(') {
                current_depth++;
                max_depth = std::max(max_depth, current_depth);
            } else if (ch == ')') {
                current_depth--;
            }
        }

        return max_depth;
    }
};

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string s. This is because we only perform a single traversal of the string.

Explanation

• We initialize two variables current_depth and max_depth to 0.
• We iterate over each character in the string s.
• For each opening parenthesis (, we increment current_depth and update max_depth if the current depth exceeds the previous max_depth.
• For each closing parenthesis ), we decrement current_depth.
• At the end of traversal, max_depth will hold the maximum depth of the nested parentheses in the string.

This approach ensures that we efficiently and accurately determine the maximum nesting depth in a single pass through the input string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?