สมมติว่าเรามีสตริง s เราต้องหาผลรวมของความสวยงามของสตริงย่อยทั้งหมด ความงามของสตริงคือความแตกต่างของความถี่ระหว่างอักขระที่ใช้บ่อยที่สุดและความถี่น้อยที่สุด ดังนั้นหากสตริงคือ "abaacc" ความถี่ของมันคือ 3 - 1 =2
ดังนั้น หากอินพุตเป็นเหมือน s ="xxyzy" ผลลัพธ์จะเป็น 5 เพราะสตริงย่อยที่มีความสวยงามไม่เป็นศูนย์คือ ["xxy","xxyz","xxyzy","xyzy","yzy"], แต่ละอันมีค่าความสวยอยู่ที่ 1.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
res:=0
-
สำหรับฉันในช่วง 0 ถึงขนาด s - 1 ทำ
-
สำหรับ j ในช่วง i+2 ถึงขนาด s - 1 ทำ
-
c:=แผนที่ที่มีความถี่อักขระของสตริงย่อยของ s จากดัชนี i ถึง j
-
v:=รายการค่าความถี่ทั้งหมดของ c
-
res :=res +(สูงสุดของ v - ต่ำสุดของ v)
-
-
-
ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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)) อินพุต
"xxyzy"
ผลลัพธ์
5
