สตริงย่อยที่ยาวที่สุดโดยไม่มีอักขระซ้ำใน Python

สมมติว่าเรามีสตริง เราต้องหาสตริงย่อยที่ยาวที่สุดโดยไม่ใช้อักขระซ้ำ ดังนั้นหากสตริงนั้นเหมือนกับ “ABCABCBB” ผลลัพธ์จะเป็น 3 เนื่องจากมีสตริงย่อยที่ทำซ้ำ ของความยาว 3 นั่นคือ “ABC”

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

• set i :=0, j :=0, ตั้งค่าหนึ่งแผนที่เพื่อเก็บข้อมูล
• ตอบ :=0
• ในขณะที่ j <ความยาวของสตริง s
  • ถ้า s[j] ไม่มีอยู่ในแผนที่ หรือ i> map[s[j]] แล้ว
    • ans :=max(ans, j – i + 1)
    • map[s[j]] :=j
  • อย่างอื่น
    • i :=map[s[j]] + 1
    • ans :=max(ans, j – i + 1)
    • ลด j ทีละ 1
  • เพิ่ม j ขึ้น 1
• คืนสินค้า

ตัวอย่าง (Python)

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

class Solution(object):
   def lengthOfLongestSubstring(self, s):
      i =0
      j = 0
      d={}
      ans = 0
      while j < len(s):
         if s[j] not in d or i>d[s[j]]:
            ans = max(ans,(j-i+1))
            d[s[j]] = j
         else:
            i = d[s[j]]+1
            ans = max(ans,(j-i+1))
            j-=1
         #print(ans)
         j+=1
      return ans
ob1 = Solution()
print(ob1.lengthOfLongestSubstring("ABCABCBB"))

อินพุต

"ABCABCBB"

ผลลัพธ์

3