Good split: แบ่ง string s เป็น p + q (p,q ไม่ว่าง) จำนวน distinct characters ใน p และ q เท่ากัน ใช้ 2 Counter: left (สะสมจากซ้าย), right (เริ่มจาก count ทั้ง s) วนลูปย้าย char จาก right ไป left ถ้า len(left) == len(right) นับ good split
ขั้นตอนการทำงาน
- left = Counter(), right = Counter(s)
- result = 0
- วนลูป c ใน s: left[c]++, right[c]-- ถ้า right[c]==0: del right[c]
- ถ้า len(left) == len(right): result++
- คืน result
ตัวอย่างโค้ด
from collections import Counter
def solve(s):
result = 0
left, right = Counter(), Counter(s)
for c in s:
left[c] += 1
right[c] -= 1
if not right[c]:
del right[c]
if len(left) == len(right):
result += 1
return result
s = "xxzxyx"
print(solve(s)) # Output: 2
อินพุต/เอาต์พุต
Input: "xxzxyx" Output: 2
Good splits: ("xxz", "xyx") distinct=2,2 และ ("xxzx", "yx") distinct=2,2
