สมมติว่าเรามีสตริงตัวพิมพ์เล็ก s เราต้องหาผลรวมของการนับอักขระที่แตกต่างกันในทุกสตริงย่อยของ s หากคำตอบมีขนาดใหญ่มาก ให้คืนค่า mod ผลลัพธ์ 10^9+7
ดังนั้น หากอินพุตเป็น s ="xxy" ผลลัพธ์จะเป็น 6 เนื่องจากสตริงย่อยและจำนวนเป็น −
-
"x" :1
-
"x" :1
-
"y" :1
-
"xx" :0 (เนื่องจาก "x" ไม่ต่างกัน)
-
"xy" :2
-
"xxy" :1 ("x" ไม่ต่างกัน)
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ม :=10^9 + 7
-
prev_seen :=แผนที่ใหม่เปล่า
-
ตอบ :=0
-
กำหนดฟังก์ชัน util() นี่จะใช้เวลา i สัญลักษณ์
-
prev_seen[สัญลักษณ์] :=รายการที่มีค่าเดียว -1
-
ก่อนหน้า :=prev_seen[สัญลักษณ์]
-
แทรก i ที่ส่วนท้ายของก่อนหน้า
-
ถ้าขนาดก่อนหน้า> 2 แล้ว
-
ซ้าย :=องค์ประกอบแรกของก่อนหน้าและลบองค์ประกอบแรกจากก่อนหน้า
-
กลาง :=ก่อนหน้า[0], ขวา :=ก่อนหน้า[1]
-
cnt :=(กลาง - ซ้าย) *(ขวา - กลาง)
-
ans :=(ans + cnt) mod m
-
-
สำหรับแต่ละดัชนี i และสัญลักษณ์ค่าใน s ทำ
-
util(i, สัญลักษณ์)
-
-
สำหรับแต่ละสัญลักษณ์ใน prev_seen ให้ทำ
-
util(ขนาดของ s , สัญลักษณ์)
-
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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
