Giả sử chúng ta có một chuỗi s. Chúng ta phải tìm tổng vẻ đẹp của tất cả các chuỗi con của nó. Vẻ đẹp của một chuỗi thực sự là sự khác biệt về tần số giữa các ký tự thường xuyên nhất và ít thường xuyên nhất. Vì vậy, nếu chuỗi là "abaacc", thì tần số của nó là 3 - 1 =2.
Vì vậy, nếu đầu vào là s ="xxyzy", thì đầu ra sẽ là 5 vì các chuỗi con có độ đẹp khác 0 là ["xxy", "xxyz", "xxyzy", "xyzy", "yzy"], mỗi cái đều có giá trị vẻ đẹp 1.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
res:=0
-
đối với tôi trong phạm vi từ 0 đến kích thước của s-1, hãy thực hiện
-
đối với j trong phạm vi i + 2 đến kích thước của s-1, thực hiện
-
c:=một bản đồ chứa các ký tự tần số của chuỗi con s từ chỉ mục i đến j
-
v:=danh sách tất cả các giá trị tần số của c
-
res:=res + (tối đa v - tối thiểu v)
-
-
-
trả lại res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
from collections import Counter
def solve(s):
res=0
for i in range(len(s)):
for j in range(i+2,len(s)):
c=Counter(s[i:j+1])
v=c.values()
res+=(max(v)-min(v))
return res
s = "xxyzy"
print(solve(s)) Đầu vào
"xxyzy"
Đầu ra
5