Nhận xét 1: Nếu độ dài \(L\) thỏa mãn thì độ dài \(L - 1\) cũng thỏa mãn.

• Chứng minh: Xét một cách chia xâu với độ dài \(L\). Bỏ đi tất cả chữ cuối trong \(k\) xâu độ dài \(L\) được chọn, chúng ta còn lại \(k\) xâu độ dài \(L - 1\) và các xâu mới này \(<\) các xâu cũ \(\leq T\).

Nhận xét 2: Chúng ta chỉ cần tìm số \(L\) lớn nhất thỏa mãn. Khi đó đáp số sẽ là \(L\). Vì vậy chúng ta có thể nghĩ đến chặt nhị phân cho \(L\). Với mỗi số \(L\), chúng ta sẽ kiểm tra xem có thể chọn được \(k\) xâu rời nhau độ dài \(L\) mà mỗi xâu \(\leq T\) hay không.

Bước kiểm tra \(L\) có thể làm như sau:

\(1.\) Đầu tiên với mỗi vị trí \(i\) từ \(0\) đến \(L_S - L\), chúng ta sẽ xem thử xâu con \(S[i..(i + L - 1)]\) có \(\leq T\) hay không. Nếu bé hơn hoặc bằng thì đánh dấu \(a[i] = 1\). Xâu con \(S[i..(i + L - 1)]\) là xâu độ dài \(L\) bắt đầu từ \(i\).

Để thực hiện bước này, nếu liệt kê các xâu con ra thì độ phức tạp sẽ là \(O(L_SL)\), quá lớn. Tuy nhiên chúng ta có thể tìm tiền tố chung dài nhất của chúng trước. Ví dụ muốn so sánh "abc" và "abbf", tiền tố chung dài nhất là "ab" nên chỉ cần so sánh chữ cái tiếp theo "c" và "b".

Để tìm tiền tố chung dài nhất của \(S[i..(i + L - 1)]\) và \(S\), chúng ta có thể dùng thuật toán Z, hoặc Hash + Chặt nhị phân. Độ phức tạp là \(O(1)\) hoặc \(O(log)\) cho mỗi \(i\).

\(2.\) Sau khi có được mảng \(a[]\), chúng ta cần chọn nhiều số \(a[i] = 1\) nhất có thể, đồng thời vị trí của chúng phải cách nhau ít nhất \(L\) đơn vị. Điều này có thể được thực hiện bằng tham lam hoặc quy hoạch động. Cuối cùng ta so sánh xem số này $ \geq k$ hay không.