algoadvance

Leetcode 1614. Maximum Nesting Depth of the Parentheses

Problem Statement

The problem “1614. Maximum Nesting Depth of the Parentheses” requires to determine the maximum nesting depth of the parentheses in a given string s. A string is a valid parentheses string (VPS) if it meets any one of the following criteria:

1. It is an empty string, which is a valid VPS with a nesting depth of 0.
2. It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
3. It can be written as (A), where A is a valid parentheses string.

Given a valid parentheses string s, the task is to return the maximum depth of nested parentheses.

Clarifying Questions

1. Input Constraints: What is the maximum length of the input string s?
   • Input string length does not exceed 100.
2. Character Set: Does the string contain only parentheses, or could there be other characters?
   • The problem guarantees that the input string s is a valid parentheses string, so it will contain only ( and ) characters.
3. Edge Cases: Should we consider empty strings?
   • Yes, according to the problem statement, an empty string is a valid VPS with a nesting depth of 0.

Strategy

To solve this problem, we’ll use a single pass traversal approach with a counter to keep track of the depth:

• Initialize currentDepth to 0 and maxDepth to 0.
• Traverse the string character by character.
• For each ( encountered, increment currentDepth. Update maxDepth whenever currentDepth exceeds the current maxDepth.
• For each ) encountered, decrement currentDepth. It ensures correctly matching the nested depth by decrementing per closed parenthesis.
• After traversing the entire string, maxDepth will hold the maximum depth of nested parentheses.

Code

public class Solution {
    public int maxDepth(String s) {
        // Initialize depth trackers
        int currentDepth = 0;
        int maxDepth = 0;
        
        // Traverse the string
        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                currentDepth++;
                if (currentDepth > maxDepth) {
                    maxDepth = currentDepth;
                }
            } else if (ch == ')') {
                currentDepth--;
            }
        }
        
        return maxDepth;
    }

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

Time Complexity

The solution traverses the string once, processing each character in constant time O(1), so the time complexity is O(n), where n is the length of the string. The space complexity is O(1) since we are using a fixed amount of extra space for the counters.

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?