Ta sẽ sử dụng quy hoạch động để giải quyết bài toán.

Với mỗi vị trí \(i\) của xâu, ta cần tính số lượng xâu con khác nhau của xâu \(s_{1, i}\) có thể tạo ra bằng các thao tác trên. Gọi \(f(i)\) là số lượng xâu con khác nhau của \(s_{1, i}\) có thể tạo ra.

Ta cần tính \(f(i)\) từ \(f(j)\) với \(j\) là vị trí gần nhất của một chuỗi aa hoặc bb ở bên phải của vị trí \(i\) (hay còn gọi là next position). Gọi \(nx_{i, 0}\) và \(nx_{i, 1}\) lần lượt là next position của aa và bb phía sau vị trí \(i\).

Từ vị trí \(i\), nếu ta chọn thay aa thì sẽ tạo ra một xâu \(s_{1, i + 1}\) có next position là \(nx_{i+1, 0}\) và nếu ta chọn thay bb thì sẽ tạo ra một xâu \(s_{1, i + 1}\) có next position là \(nx_{i+1, 1}\).

Ngoài ra, nếu tổng số lượng kí tự a của xâu \(s_{1, i}\) chia hết cho \(3\), ta còn có thể thay đổi tất cả các kí tự a thành b và ngược lại, để tạo ra một xâu con khác nữa.

Sử dụng quy hoạch động để tính \(f(i)\) cho mọi vị trí \(i\) từ cuối xâu đến đầu xâu.

Vì độ dài của xâu có thể lên đến \(2 \times 10^7\), ta cần lưu next position của aa và bb trong một mảng 2 chiều.

Độ phức tạp thuật toán: \(O(n)\) với \(n\) là độ dài của xâu.