Cho chuỗi input_str và số nguyên k. Lặp chuỗi k lần thành chuỗi mới. Tìm độ dài chuỗi con dài nhất thỏa mãn: 2 × (số 0) ≤ 3 × (số 1).
Ví dụ
Input: k=2, input_str='0101011' → Output: 14
Chuỗi mới: '01010110101011' (độ dài 14). Số 0: 6, số 1: 8. 2×6=12 ≤ 3×8=24. Toàn bộ chuỗi thỏa mãn.
Thuật toán (Prefix Sum + Binary Search)
Biến đổi điều kiện: 2×zeros - 3×ones ≤ 0. Gán trọng số: '0' → +2, '1' → -3. Tìm chuỗi con dài nhất có tổng trọng số ≤ 0.
- Tính mảng prefix sum
list_acủa trọng số - Tạo mảng
list_b= [(prefix_value, index)] và sắp xếp - Tính
temp_list: max index cho mỗi prefix value trong list_b đã sắp xếp - Duyệt từng vị trí i, dùng binary search (
bisect_left) tìm vị trí xa nhất thỏa mãn - Xử lý trường hợp lặp k lần bằng cách nhân với tổng trọng số của một chuỗi gốc
Mã nguồn
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')) # Output: 14Phân tích độ phức tạp
- Thời gian: O(L log L) với L = len(input_str)
- Không gian: O(L)
- Không phụ thuộc vào k (xử lý lặp bằng toán học)