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

The Python solution on this page runs in O(n), where n is the length of the string seq.

What is the space complexity of LeetCode 1111. Maximum Nesting Depth of Two Valid Parentheses Strings?

The Python solution on this page uses O(1) auxiliary space.

Maximum Nesting Depth of Two Valid Parentheses Strings — LeetCode 1111 Python Solution

MediumStackString

Problem: #1111
Pattern: Stack
Reading time: 2 min
Source: leetcode.com

The problem

A string is a valid parentheses string (denoted VPS) if and only if it consists of "(" and ")" characters only, and: It is the empty string, or It can be written as AB (A concatenated with B), where A and B are VPS's, or It can be written as (A), where A is a VPS. We can similarly define the nesting depth depth(S) of any VPS S as follows: depth("") = 0 depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's depth("(" + A + ")") = 1 + depth(A), where A is a VPS.

Example

Input: seq = "(()())"
Output: [0,1,1,1,1,0]

Python solution

Python

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        ans = [0] * len(seq)
        x = 0
        for i, c in enumerate(seq):
            if c == "(":
                ans[i] = x & 1
                x += 1
            else:
                x -= 1
                ans[i] = x & 1
        return ans

Complexity

Measure	Complexity
Time	O(n), where n is the length of the string seq
Space	O(1) auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 1111. Maximum Nesting Depth of Two Valid Parentheses Strings is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1111. Maximum Nesting Depth of Two Valid Parentheses Strings?: LeetCode 1111. Maximum Nesting Depth of Two Valid Parentheses Strings is rated Medium on LeetCode.
What is the time complexity of LeetCode 1111. Maximum Nesting Depth of Two Valid Parentheses Strings?: The Python solution on this page runs in O(n), where n is the length of the string seq.
What is the space complexity of LeetCode 1111. Maximum Nesting Depth of Two Valid Parentheses Strings?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1111. Maximum Nesting Depth of Two Valid Parentheses Strings cover?: LeetCode 1111. Maximum Nesting Depth of Two Valid Parentheses Strings is tagged Stack and String on LeetCode.