LeetCode Entry

1111. Maximum Nesting Depth of Two Valid Parentheses Strings

30.09.2026 medium 2026 kotlin rust

Min braces depth subsequence split

1111. Maximum Nesting Depth of Two Valid Parentheses Strings medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1498

Problem TLDR

Min braces depth subsequence split

Intuition

Greedily put brace in a group with the lower balance.

Approach

• another way: open brace olways has a group i%2, closed brace 1-i%2

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun hasValidPath(g: Array<CharArray>) = run {
        val o=Array(102){0.toBigInteger()};o[1] = 1.toBigInteger()
        for (r in g) for (x in r.indices)
            o[x+1] = (o[x] or o[x+1]).shiftLeft(81 - r[x].code * 2)
        o[g[0].size].testBit(0)
    }

    fun maxDepthAfterSplit(s: String) =
    s.indices.map { it + s[it].code and 1 }