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