ได้รับสตริงตัวพิมพ์เล็ก s ต้องแบ่งเป็นชิ้นมากที่สุดเท่าที่จะทำได้ โดยเงื่อนไข: ตัวอักษรแต่ละตัวต้องปรากฏในชิ้นเดียวเท่านั้น คืนค่าขนาดของแต่ละชิ้นเป็นลิสต์
ตัวอย่าง
Input: "momoplaykae"
Output: [4, 1, 1, 4, 1]
การแบ่ง: ["momo", "p", "l", "ayka", "e"]
ตัวอักษร 'm','o' อยู่ชิ้นแรก 'p' ชิ้นที่สอง 'l' ชิ้นที่สาม 'a','y','k' ชิ้นที่สี่ 'e' ชิ้นที่ห้า
แนวทางแก้ปัญหา
ใช้ Greedy + Stack:
- นับความถี่ของตัวอักษรทุกตัวใน
s - วนอ่านตัวอักษรทีละตัว:
- ลดจำนวนที่เหลือของตัวอักษรนั้น
- เพิ่มความยาวชิ้นปัจจุบัน
- ถ้ายังเหลือตัวอักษรนี้อีก → push เข้า stack (ยังไม่สามารถปิดชิ้นได้)
- ถ้า stack บนสุดเหลือ 0 แล้ว → pop ออก
- ถ้า stack ว่าง และตัวอักษรปัจจุบันเหลือ 0 → ปิดชิ้น บันทึกความยาว รีเซ็ต
การใช้งาน (Python)
from collections import Counter
class Solution:
def solve(self, s):
count = Counter(s)
out = []
stk = []
length = 0
for char in s:
count[char] -= 1
length += 1
while count[char] != 0 or stk:
if count[char] != 0:
stk.append(char)
break
if stk and count[stk[-1]] == 0:
stk.pop()
else:
break
if not stk and count[char] == 0:
out.append(length)
length = 0
return out
# ทดสอบ
ob = Solution()
print(ob.solve("momoplaykae")) # Output: [4, 1, 1, 4, 1]
ความซับซ้อน
- Time Complexity: O(N)
- Space Complexity: O(Alphabet) = O(1)
