กำหนดสตริงและจำนวนเต็ม k สตริงจะถูกทำซ้ำ k ครั้งเพื่อสร้างสตริงใหม่ ต้องการหาความยาวของซับสตริงที่ยาวที่สุดในสตริงใหม่ที่ทำให้ 2 × (จำนวน 0) ≤ 3 × (จำนวน 1)
ตัวอย่าง
อินพุต: k = 2, input_str = '0101011' → เอาต์พุต: 14
- สตริงต้นฉบับยาว 7 ตัวอักษร
- สตริงใหม่:
01010110101011(ยาว 14) - จำนวน 0 = 6, จำนวน 1 = 8
- 2 × 6 = 12 ≤ 3 × 8 = 24 ✓
- ซับสตริงที่ยาวที่สุดคือสตริงทั้งหมด ความยาว 14
วิธีแก้ปัญหา
- คำนวณค่า prefix sum โดยให้ '1' = -3, '0' = +2
- จัดเก็บค่า prefix sum พร้อมดัชนี แล้วเรียงลำดับ
- สร้างอาร์เรย์
temp_listสำหรับดัชนีสูงสุดสะสม - ใช้ binary search (
bisect_left) หาตำแหน่งที่เหมาะสม - พิจารณากรณีที่ซ้ำ
kครั้ง โดยใช้คุณสมบัติของ prefix sum ทั้งสตริง
ตัวอย่างโค้ด
from bisect import bisect_left
def solve(k, input_str):
str_len = len(input_str)
list_a = [0] * (str_len + 1)
list_b = [0] * (str_len + 1)
list_b[0] = (0, 0)
for i in range(str_len):
list_a[i + 1] = list_a[i] - 3 * (input_str[i] == '1') + 2 * (input_str[i] == '0')
list_b[i + 1] = (list_a[i + 1], i + 1)
list_b.sort()
temp_list = [0] * (str_len + 1)
temp_list[0] = list_b[0][1]
for i in range(str_len):
temp_list[i + 1] = max(temp_list[i], list_b[i + 1][1])
res = 0
for i in range(str_len):
tmp = list_b[0][0] - list_a[i]
if list_a[str_len] <= 0:
a = k - 1
if tmp + list_a[str_len] * a > 0:
continue
elif tmp > 0:
continue
else:
a = min(k - 1, -tmp // list_a[str_len])
v = a * list_a[str_len] - list_a[i]
b = bisect_left(list_b, (-v + 1, 0)) - 1
res = max(res, temp_list[b] - i + a * str_len)
return res
print(solve(2, '0101011'))อินพุต / เอาต์พุต
Input: 2, '0101011' Output: 14
หลักการ: แปลงปัญหาเป็นการหาช่วงที่ prefix sum ตรงตามเงื่อนไข ใช้เทคนิค two-pointer และ binary search เพื่อประสิทธิภาพ
