Trong trường hợp một chuỗi đã cho chỉ bao gồm các số 0 và 1, chúng ta có M dãy A, B không giao nhau (A <=B), cụ thể hơn là [A1, B1], [A2, B2],…, [AM, BM], Bất kỳ hai khoảng thời gian nào trong số này không trùng nhau - về mặt hình thức, trong trường hợp mỗi khoảng thời gian i, j hợp lệ sao cho i! =J, Ai
Hoạt động là để tìm một hoán vị hợp pháp hoặc hợp lệ sẽ đồng thời giữ hai điều kiện sau -
Tổng các số giữa tất cả M dãy đã cho sẽ lớn nhất.
Chuỗi sẽ là tối đa về mặt từ vựng. Chuỗi 1100 cao hơn về mặt từ vựng so với chuỗi 1001.
Trong ví dụ trên, đầu tiên chúng ta đặt 1 ở vị trí thứ nhất và thứ 2, sau đó chúng ta còn lại một ‘1’ khác,
Vì vậy, chúng tôi sử dụng nó để tối đa hóa chuỗi từ vựng và chúng tôi đặt nó ở vị trí thứ 3 và do đó việc sắp xếp lại hoàn tất.
Ví dụ
Input
11100
3
3 4
5 5
Output
00111
First we put 1’s in position 3 and 4 then in 5 as there are no 1’s left, the string formed is 00111.
Input
0000111
2
1 1
1 2
Output
1110000
