สตริงย่อยที่ยาวที่สุดโดยไม่มีตัวอักษรซ้ำ (Longest Substring Without Repeating Characters) ใน Python

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

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

• ตั้งค่า i := 0, j := 0, ตั้งค่า map หนึ่งเพื่อเก็บข้อมูล
• ans := 0
• while j < ความยาวของสตริง s
  • ถ้า s[j] ไม่อยู่ใน map หรือ 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
• คืนค่า ans

ตัวอย่าง (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"))

Input

"ABCABCBB"

Output

3