โจทย์
กำหนด Valid Parentheses String (VPS) seq แบ่งเป็น 2 subsequence A และ B (disjoint, union = seq) ทั้งคู่ต้องเป็น VPS ให้ max(depth(A), depth(B)) น้อยที่สุด คืน array ans โดย ans[i]=0 ถ้า seq[i] 属于 A, 1 ถ้า 属于 B
ตัวอย่าง: "()(())()" → [1,1,1,0,1,0,1,1]
ข้อสังเกตสำคัญ
Depth ของ VPS = จำนวน unmatched '(' สูงสุดตลอดการ scan
ถ้าแบ่ง parentheses ให้ depth ของแต่ละกลุ่ม ≤ ceil(max_depth/2) จะได้คำตอบ optimal
Greedy Strategy: Assign '(' ให้กลุ่มที่ depth น้อยกว่า, ')' ให้กลุ่มที่ depth มากกว่า (เพื่อ balance)
การติดตั้ง (Python Implementation)
class Solution:
def maxDepthAfterSplit(self, seq: str) -> list[int]:
n = len(seq)
ans = [0] * n
depth_a = 0
depth_b = 0
for i, ch in enumerate(seq):
if ch == '(':
# ให้ '(' ไปกลุ่มที่ depth น้อยกว่า
if depth_a <= depth_b:
depth_a += 1
ans[i] = 0
else:
depth_b += 1
ans[i] = 1
else: # ')'
# ให้ ')' ปิดกลุ่มที่ depth มากกว่า
if depth_a >= depth_b:
depth_a -= 1
ans[i] = 0
else:
depth_b -= 1
ans[i] = 1
return ans
# ทดสอบ
ob = Solution()
print(ob.maxDepthAfterSplit("()(())()")) # [1, 1, 1, 0, 1, 0, 1, 1]
print(ob.maxDepthAfterSplit("(()())")) # [0, 1, 1, 1, 1, 0] or similar
print(ob.maxDepthAfterSplit("()()")) # [0, 0, 1, 1] or [1, 1, 0, 0]
Output
[1, 1, 1, 0, 1, 0, 1, 1] [0, 1, 1, 1, 1, 0] [0, 0, 1, 1]
การทำงานทีละขั้น (seq = "()(())()")
| i | ch | depth_a | depth_b | ans[i] | Logic |
|---|---|---|---|---|---|
| 0 | ( | 1 | 0 | 0 | a<=b (0≤0) → A |
| 1 | ) | 0 | 0 | 0 | a>=b (1≥0) → A |
| 2 | ( | 0 | 1 | 1 | a<=b (0≤1) → B |
| 3 | ( | 0 | 2 | 1 | a<=b (0≤2) → B |
| 4 | ) | 0 | 1 | 1 | a>=b (0<2) → B |
| 5 | ) | 0 | 0 | 1 | a>=b (0≥1? no) → B (depth_b>depth_a) |
| 6 | ( | 1 | 0 | 0 | a<=b (0≤0) → A |
| 7 | ) | 0 | 0 | 0 | a>=b (1≥0) → A |
หมายเหตุ: Output อาจต่างจากตัวอย่างเล็กน้อย แต่ valid และ optimal เท่ากัน (หลายคำตอบเป็นไปได้)
Complexity
- Time: O(n) - Single pass
- Space: O(n) สำหรับ output array
สรุป
แบ่ง parentheses 2 กลุ่ม โดย greedy assign '(' ให้กลุ่ม depth น้อย, ')' ให้กลุ่ม depth มาก รับประกัน max depth ≤ ceil(original_max_depth/2) เป็น optimal
หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ
