คำอธิบายปัญหา
กำหนดสตริงไบนารี s หาจำนวน substring ที่ประกอบด้วย **'1' เท่านั้น** Modulo 10^9+7
ตัวอย่าง
s = "100111" → Output: 7
Substrings: "1" (4 ครั้ง), "11" (2 ครั้ง), "111" (1 ครั้ง) = 7
ขั้นตอนการแก้ปัญหา (O(n))
- วนลูปตัวอักษร: ตัวนับ
a= ความยาว streak ของ '1' ติดต่อกัน - เจอ '0' →
a = 0 - เจอ '1' →
a += 1, count += a(เพิ่ม substring ทุกค่าที่จบที่ตำแหน่นี้)
การตนการทำงาน (Python)
def solve(s):
a = 0
count = 0
for i in range(len(s)):
if s[i] == "0":
a = 0
else:
a += 1
count += a
return count
s = "100111"
print(solve(s)) # Output: 7
อินพุต / เอาต์พุต
Input: "100111" Output: 7
