โปรแกรมหาจำนวนสตริงย่อยไม่ทับซ้อนสูงสุดใน Python

สมมติว่าเรามีสตริง s ที่มีเฉพาะตัวอักษรพิมพ์เล็ก เราต้องหาจำนวนสตริงย่อยที่ไม่ว่างของ s สูงสุดที่ตรงตามกฎ:

• สตริงย่อยไม่ทับซ้อนกัน
• สตริงย่อยที่มีตัวอักษร ch ต้องมีการปรากฏของ ch ทั้งหมด

เราต้องหาจำนวนสตริงย่อยสูงสุดที่ตรงตามเงื่อนไขทั้งสอง ถ้ามีคำตอบมากกว่าหนึ่งที่มีจำนวนสตริงย่อยเท่ากัน ให้ return คำตอบที่มีความยาวรวมน้อยที่สุด

เช่น ถ้าอินพุตคือ s = "pqstpqqprrr" ผลลัพธ์จะเป็น ["s","t","rrr"] เพราะสตริงย่อยที่เป็นไปได้ทั้งหมดคือ ["pqstpqqprrr", "pqstpqqp", "st", "s", "t", "rrr"]

วิธีแก้ปัญหา

• right := เรียงรายการตำแหน่งดัชนีของตัวอักษรแต่ละตัว ch จากขวาของ s
• left := รายการดัชนีของตัวอักษร s[i] สำหรับทุก i ใน right
• has := รายการว่าง, gen := รายการว่าง
• สำหรับ i ในช่วง 0 ถึงขนาดของ right - 1:
  • เพิ่มเซตใหม่ของตัวอักษรจาก s[right[i]] ลงท้าย gen
  • เพิ่มเซตใหม่ของตัวอักษรจากสตริงย่อย s[left[i]+1 ถึง right[i]-1] ลบ gen ตัวสุดท้าย ลงท้าย has
  • สำหรับ j ในช่วงขนาดของ has - 2 ถึง 0 ลดทีละ 1:
    • ถ้า (has ตัวสุดท้าย AND gen[j]) และ (has[j] AND gen ตัวสุดท้าย) ไม่เป็นศูนย์:
      • gen ตัวสุดท้าย := gen ตัวสุดท้าย OR gen[j]
      • has ตัวสุดท้าย := (has ตัวสุดท้าย OR has[j]) - gen ตัวสุดท้าย
      • ลบ has[j], gen[j]
• res := รายการใหม่, p_right := -1
• สำหรับ ind ในช่วง 0 ถึงขนาดของ has - 1:
  • l := min ของรายการ i สำหรับทุก i ใน left ถ้า s[i] อยู่ใน gen[ind]
  • r := max ของรายการ i สำหรับทุก i ใน right ถ้า s[i] อยู่ใน gen[ind]
  • ถ้า p_right < l: เพิ่มสตริงย่อย s[l ถึง r] ลงท้าย res, p_right := r
• return res

ตัวอย่าง

def solve(s):
    right = sorted([s.rindex(ch) for ch in set(s)])
    left = [s.index(s[i]) for i in right]
    has, gen = [], []
    for i in range(len(right)):
        gen.append(set(s[right[i]]))
        has.append(set(s[left[i] + 1:right[i]]) - gen[-1])
    for j in range(len(has) - 2, -1, -1):
        if (has[-1] & gen[j]) and (has[j] & gen[-1]):
            gen[-1] = gen[-1] | gen[j]
            has[-1] = (has[-1] | has[j]) - gen[-1]
            del has[j], gen[j]
    res, p_right = [], -1
    for ind in range(len(has)):
        l = min([i for i in left if s[i] in gen[ind]])
        r = max([i for i in right if s[i] in gen[ind]])
        if p_right < l:
            res.append(s[l : r + 1])
            p_right = r
    return res

s = "pqstpqqprrr"
print(solve(s))

อินพุต

"pqstpqqprrr"

เอาต์พุต

['s', 't', 'rrr']