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

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

• สตริงย่อยไม่ทับซ้อนกัน

• สตริงย่อยที่มีอักขระเฉพาะ ch ต้องมี ch เกิดขึ้นทั้งหมดด้วย

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

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

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

• right :=เรียงลำดับรายการตำแหน่งดัชนีของอักขระแต่ละตัว ch จากด้านขวาของ s

• ซ้าย :=รายการดัชนีของตัวละคร s[i] ทั้งหมด i ทางขวา

• มี :=รายการว่าง gen :=รายการว่าง

• สำหรับฉันในช่วง 0 ถึงขนาดด้านขวา - 1 ทำ

  • ใส่ชุดอักขระใหม่จาก s[right[i]] ที่ส่วนท้ายของ gen

  • แทรกชุดอักขระใหม่จากสตริงย่อยของ s[จากดัชนี (left[i] + 1 ถึง right[i]-1] - รายการสุดท้ายของ gen) ต่อท้าย has

  • สำหรับ j ในช่วงขนาดมี - 2 ถึง 0, ลดลง 1 ทำ

    • ถ้า (รายการสุดท้ายของ has AND gen[j]) และ (มี[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 :=ขั้นต่ำของรายการองค์ประกอบ i สำหรับ i ทั้งหมดที่เหลืออยู่ หาก s[i] มีอยู่ใน gen[ind]

  • r :=สูงสุดของรายการองค์ประกอบ i สำหรับทุก i ถ้า s[i] ใน gen[ind]]

  • ถ้า p_right

    • แทรกสตริงย่อยของ s[จากดัชนี l ถึง r] ที่ส่วนท้ายของความละเอียด

    • p_right :=r

• ผลตอบแทน

ตัวอย่าง

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

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']