Chuỗi con dài nhất không có ký tự lặp lại trong Python

Giả sử chúng ta có một chuỗi. Chúng ta phải tìm chuỗi con dài nhất không lặp lại các ký tự. Ví dụ, nếu chuỗi là "ABCABCBB", kết quả sẽ là 3, vì có chuỗi con lặp lại độ dài 3 là "ABC".

Để giải quyết, chúng ta làm theo các bước:

• set i := 0, j := 0, tạo một map để lưu thông tin
• ans := 0
• while j < độ dài chuỗi s
  • nếu s[j] không có trong map, hoặc i > map[s[j]], thì
    • ans := max(ans, j - i + 1)
    • map[s[j]] := j
  • ngược lại
    • i := map[s[j]] + 1
    • ans := max(ans, j - i + 1)
    • giảm j đi 1
  • tăng j lên 1
• trả về ans

Ví dụ (Python)

Hãy xem triển khai sau để hiểu rõ hơn:

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