Một số điều cần lưu ý: Xâu $s$ và $t$ có thể chứa dấu khoảng trắng.

Subtask 1

Hiển nhiên rằng, lời giải tối ưu sẽ không bao gồm việc thêm một ký tự rồi xóa đi chính ký tự đó hoặc ngược lại, ví dụ xâu aa, nếu thêm vào ký tự s để trở thành xâu asa, sau đấy lại xóa chính ký tự s đấy để trở lại thành xâu aa, hoặc ngược lại. Do đó, ta hoàn toàn có thể chuyển các thao tác xóa lên đầu tiên, và sau khi thực hiện tất cả các thao tác xóa, xâu nhận được sẽ là xâu con của $s$ và ta phải thêm một vài ký tự để nó trở thành xâu $t$, nghĩa là xâu đó phải là xâu con chung của $s$ và $t$.

Đến đây, ta có thể duyệt đệ quy từng xâu con của $s$ và kiểm tra xem nó có phải xâu con của $t$ hay không. Độ phức tạp: $O(2^{|s|}\times t)$.

Subtask 2

Từ nhận xét ở subtask 1, ta nhận thấy rằng đây là một bài toán LCS cổ điển, vì ta biết rằng, để mất ít thao tác xóa/thêm nhất, ta phải giữ lại số ký tự nhiều nhất, và những ký tự được giữ lại sẽ là xâu con chung dài nhất của $s$ và $t$. Độ phức tạp: $O(|s| \times |t|)$.

Lưu ý độ phức tạp nếu cài LCS theo cách quy hoạch động hai chiều cũng là $|s| \times |t|$, và đây chính là sự khác biệt giữa subtask này và subtask 3.

Subtask 3

Subtask này đòi hỏi các bạn phải sử dụng một kỹ thuật đó là LCS với giới hạn bộ nhớ $O(|t|)$ cho mảng quy hoạch động. Ý tưởng của kỹ thuật này như sau:

Biến độ dài xâu $t$ thành thứ tự for, và gọi $dp[i]$ là độ dài xâu con chung dài nhất có thể tạo được khi xét đến vị trí $i$ trong xâu $t$ và vị trí đang được for trong xâu $s$.

Ví dụ như chúng ta đang for đến vị trí thứ $4$ trong xâu $s$ thì $dp[5]$ lúc này sẽ có vai trò như $dp[4][5]$ trong cách dp cổ điển.

Như vậy chúng ta đã có thể tối ưu được bài toán LCS xuống bộ nhớ $O(|t|)$ và độ phức tạp $O(|s| \times |t|)$.

Dưới đây là đoạn code dp cho subtask này:

for(int i = 0; i < s.size(); i ++)
{
    for(int j = t.size() - 1; j >= 0; j --)
        if(s[i] == t[j]) dp[j + 1] = max(dp[j + 1], dp[j] + 1);
    for(int j = 0; j < t.size(); j ++)
        dp[j + 1] = max(dp[j + 1], dp[j]);
}