Chương trình tìm độ dài của chuỗi con dài nhất có hai phần tử riêng biệt trong Python

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm độ dài của chuỗi con dài nhất chứa ít nhất 2 ký tự khác nhau.

Vì vậy, nếu đầu vào là s =​​"xyzzy", thì đầu ra sẽ là 4, vì "yzzy" là chuỗi con dài nhất với nhiều nhất là 2 ký tự duy nhất.

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

• bắt đầu:=0

• c:=một bản đồ

• ans:=0

• để kết thúc trong phạm vi 0 đến kích thước của s, thực hiện

  • c [s [end]]:=c [s [end]] + 1

  • trong khi kích thước c> 2, làm

    • c [s [start]]:=c [s [start]] - 1

      
      

    • nếu c [s [start]] là 0 thì

      • xóa c [s [start]]

    • start:=start + 1

  • ans:=tối đa ans và (end - start + 1)

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

class Solution:
   def solve(self, s):
      from collections import Counter
      start = 0
      c = Counter()
      ans = 0
      for end in range(len(s)):
         c[s[end]] += 1
         while len(c) > 2:
            c[s[start]] -= 1
            if not c[s[start]]:
               del c[s[start]]
            start += 1
         ans = max(ans, end - start + 1)
      return ans
ob = Solution()
s = "xyzzy"
print(ob.solve(s))

Đầu vào

s = "xyzzy"

Đầu ra

4