LeetCode 1111: Maximum Nesting Depth of Two Valid Parentheses Strings Solution

Master LeetCode problem 1111 (Maximum Nesting Depth of Two Valid Parentheses Strings), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1111. Maximum Nesting Depth of Two Valid Parentheses Strings

Medium

String Stack

Problem Explanation

Explanation

To solve this problem, we need to split the given valid parentheses string (seq) into two disjoint subsequences (A and B) such that the maximum depth of the two subsequences is minimized. We can achieve this by allocating parentheses alternatively to subsequences A and B. This way, we can balance the nesting depth between the two subsequences.

Algorithmic Idea

Iterate over the characters in the input string seq.
Assign the characters to subsequences A and B alternatively based on their index.
Whenever we encounter an opening parenthesis (, we increment the depth counter.
To balance the depth between A and B, we assign the character to the subsequence with the lower current depth.
Return the resulting answer array.

Time Complexity

The time complexity of this algorithm is O(n), where n is the length of the input string seq.

Space Complexity

The space complexity is O(n) to store the answer array.

Solution Code

class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int n = seq.length();
        int[] ans = new int[n];
        int depth = 0;
        
        for (int i = 0; i < n; i++) {
            char c = seq.charAt(i);
            if (c == '(') {
                depth++;
                ans[i] = depth % 2;
            } else {
                ans[i] = depth % 2;
                depth--;
            }
        }
        
        return ans;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1111 (Maximum Nesting Depth of Two Valid Parentheses Strings)?

This page provides optimized solutions for LeetCode problem 1111 (Maximum Nesting Depth of Two Valid Parentheses Strings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1111 (Maximum Nesting Depth of Two Valid Parentheses Strings)?

The time complexity for LeetCode 1111 (Maximum Nesting Depth of Two Valid Parentheses Strings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1111 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1111 in Java, C++, or Python.

Back to LeetCode Solutions