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 mà không lặp lại các ký tự. Vì vậy, nếu chuỗi giống như "ABCABCBB", thì kết quả sẽ là 3, vì có một chuỗi con đang lặp lại, có độ dài 3. Đó là "ABC".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau

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

Ví dụ (Python)

Hãy cùng chúng tôi xem cách 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"))

Đầu vào

"ABCABCBB"

Đầu ra

3