คำอธิบายโจทย์
ให้สตริง s ตัวพิมพ์เล็ก หาผลรวมของจำนวนตัวอักษรที่ distinct (ปรากฏครั้งเดียว) ในทุก substring ของ s ผลลัพธ์ mod 10^9+7
ตัวอย่าง
s = "xxy" → เอาต์พุต: 6
Substrings: "x"(1), "x"(1), "y"(1), "xx"(0), "xy"(2), "xxy"(1) = 6
วิธีแก้ปัญหา
Contribution Technique (นับส่วนร่วมของแต่ละตัวอักษร):
- ตัวอักษรแต่ละตัวมีส่วนร่วมต่อ substring ที่มันเป็น distinct
- สำหรับตัวอักษรที่ปรากฏหลายครั้ง: พิจารณา 3 ตำแหน่งติดกัน (left, middle, right)
- จำนวน substring ที่ middle เป็น distinct = (middle - left) * (right - middle)
- ใช้ dictionary เก็บตำแหน่งล่าสุด 3 ตัวของแต่ละตัวอักษร
โค้ด Python
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))
อินพุต
xxy
เอาต์พุต
6
