LeetCode 1614: Maximum Nesting Depth of the Parentheses

Explanation

To find the maximum nesting depth of parentheses in a given valid parentheses string, we can use a simple algorithm. We iterate through the string character by character and maintain a count of open parentheses. The maximum depth encountered during this iteration will be our answer.

Algorithm:

1. Initialize variables maxDepth and currentDepth to 0.
2. Iterate through each character in the input string.
3. If the character is an opening parenthesis '(', increment currentDepth by 1.
4. Update maxDepth to be the maximum of maxDepth and currentDepth.
5. If the character is a closing parenthesis ')', decrement currentDepth by 1.
6. Return maxDepth as the result.

Time Complexity: O(n) where n is the length of the input string. Space Complexity: O(1) as we are using constant extra space.

class Solution {
    public int maxDepth(String s) {
        int maxDepth = 0;
        int currentDepth = 0;
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                currentDepth++;
                maxDepth = Math.max(maxDepth, currentDepth);
            } else if (c == ')') {
                currentDepth--;
            }
        }
        
        return maxDepth;
    }
}