โปรแกรมแบ่งสตริงเป็น k ส่วนที่ไม่ซ้ำกันใน Python

สมมติว่าเรามีสตริง s และค่า k โดย k เป็น因數ของความยาว s (สมมติความยาวคือ n) เราสามารถแบ่ง s เป็น n/k สตริงย่อย t_i ขนาด k แล้วจาก t_i สร้าง u_i โดยที่:

• ตัวอักษรใน u_i เป็น subsequence ของ t_i
• ลบตัวอักษรซ้ำออก ทำให้ความถี่ของแต่ละตัวอักษรใน u_i เป็น 1

ตัวอย่างเช่น s = "MMPQMMMRM" k = 3 ผลลัพธ์ = ["MP", "QM", "MR"] เพราะความยาว 9 หาร 3 ได้ 3 ส่วน: MMP, QMM, MRM -> ลบซ้ำ -> MP, QM, MR

ขั้นตอนการแก้ปัญหา

• i := 0, ret := [], mp := {}, to_print := ""
• while i < len(s):
  • ถ้า i % k == 0 และ i != 0: เพิ่ม to_print เข้า ret, ล้าง mp และ to_print
  • ถ้า s[i] ไม่อยู่ใน mp: mp[s[i]] = 0, to_print += s[i]
  • i += 1
• เพิ่ม to_print เข้า ret สุดท้าย
• คืนค่า 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:
            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']