Maximum Nesting Depth of Two Valid Parentheses Strings: Tách Chuỗi Ngoặc Để Minimize Độ Sâu Tối Đa

Đề bài: Cho VPS (Valid Parentheses String) seq. Tách thành 2 subsequence A, B (disjoint, union = seq) sao cho cả 2 đều là VPS và max(depth(A), depth(B)) tối thiểu. Trả về mảng ans[i] = 0/1 đánh dấu ký tự thuộc A/B.

Ví dụ: "()(())()" → [1,1,1,0,1,0,1,1].

Quan sát: Greedy phân phối theo độ sâu hiện tại

Duyệt seq, giữ 2 counter depth_A, depth_B (số '(' chưa đóng của A/B).

• Gặp '(': gán cho nhóm có depth nhỏ hơn (để cân bằng). Nếu bằng nhau → gán cho B (tùy convention).
• Gặp ')': gán cho nhóm đang có depth lớn hơn (để đóng ngoặc đúng nhóm).

Điều này đảm bảo depth chênh lệch ≤ 1 → max depth tối thiểu.

Code Python

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> list[int]:
        n = len(seq)
        res = [0] * n
        depth_a = depth_b = 0
        
        for i, ch in enumerate(seq):
            if ch == '(':
                if depth_a < depth_b:
                    depth_a += 1
                    res[i] = 0
                else:
                    depth_b += 1
                    res[i] = 1
            else:  # ')'
                if depth_a > depth_b:
                    depth_a -= 1
                    res[i] = 0
                else:
                    depth_b -= 1
                    res[i] = 1
        
        return res

# Test
ob = Solution()
print(ob.maxDepthAfterSplit("()(())()"))  # [1, 1, 1, 0, 1, 0, 1, 1]
print(ob.maxDepthAfterSplit("((()))"))    # [0, 0, 0, 1, 1, 1] hoặc tương tự

Chứng minh tính đúng đắn

• Luôn gán '(' cho depth nhỏ hơn → depth chênh lệch ≤ 1.
• Luôn gán ')' cho depth lớn hơn → đóng ngoặc đúng nhóm (không bao giờ đóng nhóm depth=0).
• Kết quả: max depth = ceil(original_depth / 2).

Phân tích

• Time: O(n)
• Space: O(n) cho kết quả (O(1) extra)
• Single pass, greedy optimal.

Kết luận

Bài toán cân bằng độ sâu 2 VPS con. Greedy theo depth hiện tại là tối ưu. Pattern: maintain counters, assign based on current state.