โปรแกรมหาขนาดของแต่ละพาร์ติชั่นของรายการที่แต่ละตัวอักษรปรากฏไม่เกินหนึ่งชิ้นในPython

สมมติว่าเรามีสตริงตัวพิมพ์เล็ก s เราสามารถแบ่งพาร์ติชัน s ออกเป็นหลายส่วนได้มากที่สุดเท่าที่เป็นไปได้ โดยให้แต่ละตัวอักษรปรากฏไม่เกินหนึ่งชิ้น และค้นหาขนาดของพาร์ติชั่นเป็นรายการ

ดังนั้น หากอินพุตเป็น s ="momoplaykae" ผลลัพธ์จะเป็น [4, 1, 1, 4, 1] เนื่องจากสตริงถูกแบ่งออกเป็น ["momo", "p", "l", " อายะ”, “อี”].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• count :=แผนที่ที่มีอักขระใน s และการเกิดขึ้นของพวกมัน

• out :=รายการใหม่ stk :=สแต็กว่าง

• ความยาว :=0

• สำหรับแต่ละอักขระใน s ทำ

  • count[char] :=count[char] - 1

  • ความยาว :=ความยาว + 1

  • ในขณะที่ count[char] ไม่เหมือนกับ 0 หรือ stk ไม่ว่างเปล่าให้ทำ

    • ถ้า count[char] ไม่เหมือนกับ 0 แล้ว

      • ดันถ่านเข้า stk

      • ออกจากวง

    • ถ้า stk ไม่ว่างและ count[top of stk] เท่ากับ 0 แล้ว

      • ป๊อปจาก stk

    • มิฉะนั้น

      • ออกจากวง

  • ถ้า stk ว่างเปล่าและ count[char] เท่ากับ 0 แล้ว

    • ใส่ความยาวหลังจากออก

    • ความยาว :=0

• กลับออกมา

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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 += [length]
               length = 0
         return out
ob = Solution()
s = "momoplaykae"
print(ob.solve(s))

อินพุต

"momoplaykae"

ผลลัพธ์

[4, 1, 1, 4, 1]