โปรแกรมค้นหาสตริงย่อยที่ใหญ่ที่สุดระหว่างอักขระสองตัวที่เท่ากันใน Python

สมมติว่าเรามีสตริง s เราต้องหาความยาวของสตริงย่อยที่ยาวที่สุดระหว่างตัวอักษรหรือองค์ประกอบที่เท่ากันสองตัว ไม่รวมอักขระสองตัว หากเราไม่พบสตริงย่อยดังกล่าว ให้คืนค่า -1

ดังนั้น หากอินพุตเป็น s ="ระดับ" เอาต์พุตจะเป็น 3 เนื่องจากสตริงย่อยที่เหมาะสมที่สุดอาจเป็น "lev" หรือ "vel"

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

• บันทึก :=แผนที่ใหม่

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

  • ถ้า s[i] อยู่ในบันทึกแล้ว

    • ใส่ i ที่ท้ายบันทึก[s[i]]

  • มิฉะนั้น

    • memo[s[i]] :=รายการที่มีองค์ประกอบเดียว i

• ดีที่สุด :=0

• สำหรับแต่ละคีย์ในบันทึกช่วยจำ ให้ทำ

  • best :=maximum of best และ (องค์ประกอบสุดท้ายของ memo[key] - องค์ประกอบแรกของ memo[key])

• ผลตอบแทนดีที่สุด - 1

ตัวอย่าง (Python)

def solve(s):
   memo = {}
   for i in range(len(s)):
      if s[i] in memo:
         memo[s[i]].append(i)
      else:
         memo[s[i]] = [i]

   best = 0
   for key in memo:
      best = max(best, memo[key][-1] - memo[key][0])
   return best - 1

s = "level"
print(solve(s))

อินพุต

"level"

ผลลัพธ์

3