Giả sử chúng ta có một chuỗi chữ thường s, chúng ta phải tìm tổng số các ký tự phân biệt trong mỗi chuỗi con của s. Nếu câu trả lời là rất lớn thì trả về kết quả mod 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là s ="xxy", thì đầu ra sẽ là 6, vì các chuỗi con và số lượng của chúng là -
-
"x":1
-
"x":1
-
"y":1
-
"xx":0 (vì "x" không khác biệt)
-
"xy":2
-
"xxy":1 ("như" x "không khác biệt)
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
m:=10 ^ 9 + 7
-
pres_seen:=một bản đồ trống mới
-
ans:=0
-
Định nghĩa một hàm dùng (). Điều này sẽ lấy tôi, ký hiệu
-
trước_seen [biểu tượng]:=danh sách có một giá trị −1
-
trước:=prev_seen [biểu tượng]
-
chèn tôi vào cuối trước
-
nếu kích thước của trước> 2, thì
-
left:=phần tử đầu tiên của trước và xóa phần tử đầu tiên khỏi trước
-
giữa:=trước [0], phải:=trước [1]
-
cnt:=(giữa - trái) * (phải - giữa)
-
ans:=(ans + cnt) mod m
-
-
đối với mỗi chỉ số i và ký hiệu giá trị trong s, thực hiện
-
sử dụng (i, ký hiệu)
-
-
đối với mỗi ký hiệu trong prev_seen, thực hiện
-
sử dụng (kích thước của s, ký hiệu)
-
-
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):
m = 10 ** 9 + 7
prev_seen = {}
ans = 0
def util(i, symbol):
nonlocal ans
prev = prev_seen.setdefault(symbol, [−1])
prev.append(i)
if len(prev) > 2:
left = prev.pop(0)
middle, right = prev
cnt = (middle − left) * (right − middle)
ans = (ans + cnt) % m
for i, symbol in enumerate(s):
util(i, symbol)
for symbol in prev_seen:
util(len(s), symbol)
return ans
ob = Solution()
s = "xxy"
print(ob.solve(s)) Đầu vào
xxy
Đầu ra
6