โปรแกรม Python เพื่อแยกสตริงออกเป็น k พาร์ติชั่นที่แตกต่างกัน

สมมติว่าเรามีสตริง s และ และค่า k ค่าของ k คือตัวประกอบของความยาวของ s สมมุติว่าความยาวคือ n เราสามารถแบ่ง s เป็น n/k สตริงย่อยที่แตกต่างกันซึ่งเรียกว่า t_i ของขนาด k จากนั้นใช้ t_i เหล่านี้เพื่อทำให้ u_i เป็นอย่างนั้น

• อักขระที่แสดงใน u_i เป็นผลสืบเนื่องมาจากอักขระใน t_i

• อักขระที่ซ้ำกันจะถูกลบออกจากสตริงเหล่านี้เพื่อให้ความถี่ของอักขระแต่ละตัวใน u_i คือ 1

เราต้องหาสตริง u_i เหล่านี้ให้เจอ

ดังนั้น หากอินพุตเท่ากับ s ="MMPQMMMRM" k =3 เอาต์พุตจะเป็น ["MP", "QM", "MR"] เนื่องจากขนาดของ s คือ 9 และ k คือ 3 ดังนั้น 9/ 3 =3 สตริงคือ MMP, QMM และ MRM แต่เนื่องจากเราไม่รองรับอักขระที่ซ้ำกัน สตริงเหล่านั้นจึงเป็น MP, QM และ MR

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

• ผม :=0
• ret :=รายการใหม่
• mp :=แผนที่ใหม่
• to_print :=สตริงว่าง
• ในขณะที่ฉัน <ขนาดของ s ทำ
  • ถ้าฉัน mod k เหมือนกับ 0 และฉันไม่ใช่ 0 แล้ว
    • แทรก to_print ที่ส่วนท้ายของ ret
    • ล้าง mp และล้าง to_print
  • ถ้า s[i] ไม่มีอยู่ใน mp แล้ว
    • mp[s[i]] :=0
    • to_print :=to_print + s[i]
  • ผม :=ผม + 1
• แทรก to_print ที่ส่วนท้ายของ ret
• คืนสินค้า

ตัวอย่าง

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

def solve(s, k):
   i = 0
   ret = []
   mp, to_print = {}, ""
   while i < len(s):
      if i % k == 0 and i != 0:
         ret.append(to_print)
         mp, to_print = {}, ""
      if s[i] not in mp.keys():
         mp[s[i]] = 0
         to_print += s[i]
      i += 1
   ret.append(to_print)
   return ret

s = "MMPQMMMRM"
k = 3
print(solve(s, k))

อินพุต

"MMPQMMMRM", 3

ผลลัพธ์

['MP', 'QM', 'MR']