Cho mảng arr (hoán vị 1..n), chuỗi nhị phân ban đầu toàn 0. Bước i: đặt bit arr[i] = 1. Tìm bước cuối cùng tồn tại nhóm 1 liên tiếp độ dài đúng m. Nhóm = substring 1 không mở rộng được. Không có thì trả -1.
Ví dụ: arr=[3,5,1,2,4], m=3 → bước 4 (00100 → 00101 → 10101 → 11101 có nhóm "111").
Thuật toán
- n = len(arr), num=0, ans=-1
- Mảng l, r kích thước n khởi tạo 0 (lưu độ dài nhóm 1 bên trái/phải)
- Duyệt i từ 0 đến n-1:
- cur=1, idx=arr[i]-1
- Nếu r[idx]==m hoặc l[idx]==m: num--
- cur += l[idx] + r[idx]; num += (cur==m)
- Nếu num>0: ans = max(ans, i+1)
- Cập nhật l, r cho biên nhóm mới
- Return ans
Code Python
def solve(arr, m):
n = len(arr)
num = 0
ans = -1
l = [0] * n
r = [0] * n
for i in range(n):
cur = 1
idx = arr[i] - 1
if r[idx] == m: num -= 1
if l[idx] == m: num -= 1
cur += l[idx] + r[idx]
num += cur == m
if num > 0:
ans = max(ans, i + 1)
if idx - l[idx] > 0:
r[idx - l[idx] - 1] = cur
if idx + r[idx] < n - 1:
l[idx + r[idx] + 1] = cur
return ans
arr = [3,5,1,2,4]
m = 3
print(solve(arr, m))
Input
[3,5,1,2,4], 3
Output
4