Hiểu bài toán

Xét một xâu ký tự S độ dài N. Ta được phép xóa tối đa k ký tự (k xóa từ bất kỳ vị trí nào). Sau khi xóa, ta thu được một xâu mới T. Vấn đề yêu cầu tìm xâu T có độ dài lớn nhất (tức là xóa ít ký tự nhất có thể nhưng không được quá k) sao cho T là một xâu đối xứng (palindrome). Nếu có nhiều xâu thỏa mãn, in ra xâu đầu tiên tìm thấy (theo thứ tự ưu tiên từ xóa nhiều ở bên trái sang bên phải). Nếu không tìm thấy xâu nào, in ra "No".

Tóm tắt yêu cầu: Tìm một xâu con liên tiếp của S độ dài L >= N - k sao cho xâu con đó là palindrome.

Các cách tiếp cận

Cách Brute Force Duyệt tất cả các cách xóa

for(int l=0;l<=k;l++){
    int r=k-l;
    if(l+r>=n) continue;
    string t=s.substr(l,n-l-r);
    if(pal(t)){
        cout<<t;
        return 0;
    }
}
cout<<"No";

• Time Complexity: O(k * N * N)
• Space Complexity: O(N)

Đây là cách tiếp cận trực quan nhất. Vì ta được phép xóa tối đa k ký tự, ta có thể chia số ký tự xóa thành 2 phần: xóa l ký tự ở đầu (bên trái) và r ký tự ở cuối (bên phải), sao cho l + r <= k.

1. Duyệt qua tất cả các giá trị l từ 0 đến k.
2. Tính r = k - l (hoặc duyệt r sao cho l + r <= k, nhưng code dùng r = k - l để tối ưu số lần duyệt).
3. Nếu l + r >= N, nghĩa là xóa quá số ký tự cho phép hoặc xóa hết xâu, bỏ qua.
4. Xâu còn lại sẽ là xâu con liên tiếp từ vị trí l đến vị trí N - 1 - r (độ dài N - l - r). Ta dùng hàm substr để lấy xâu này.
5. Kiểm tra xâu con đó có phải là palindrome không. Nếu có, in ra và kết thúc.
6. Nếu duyệt hết mà không tìm thấy, in "No".

Lưu ý: Code nộp thực tế có độ phức tạp O(k * N * N) do việc kiểm tra palindrome pal(t) mất O(N) và substr cũng mất O(N). Với k nhỏ và N nhỏ (< 1000), cách này chạy được.

Cách Optimized Brute Force (Duyệt xâu con và kiểm tra)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k; 
    cin >> n >> k;
    string s; 
    cin >> s;

    // Duyệt độ dài xâu con giảm dần từ n - k đến n
    for (int len = n - k; len <= n; len++) {
        // Duyệt tất cả các xâu con độ dài len
        for (int i = 0; i <= n - len; i++) {
            // Kiểm tra xem có thể tạo ra xâu con từ i, độ dài len không?
            // Số ký tự xóa cần thiết là (n - len).
            // Điều kiện là i xóa bên trái và (n - (i + len)) xóa bên phải phải <= k.
            int left_deleted = i;
            int right_deleted = n - (i + len);

            if (left_deleted + right_deleted <= k) {
                // Kiểm tra palindrome
                bool ok = true;
                for (int x = 0; x < len / 2; x++) {
                    if (s[i + x] != s[i + len - 1 - x]) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    cout << s.substr(i, len);
                    return 0;
                }
            }
        }
    }
    cout << "No";
}

• Time Complexity: O(N^3)
• Space Complexity: O(1)

Cách tiếp cận này tập trung vào việc tìm xâu con đối xứng trực tiếp.

1. Vì muốn xâu dài nhất, ta ưu tiên duyệt độ dài len giảm dần (từ N - k đến N).
2. Với mỗi độ dài len, duyệt tất cả các vị trí bắt đầu i (từ 0 đến N - len).
3. Với mỗi xâu con s[i...i+len-1], kiểm tra xem có thể tạo ra nó bằng cách xóa tối đa k ký tự hay không.
   • Số ký tự xóa bên trái là i.
   • Số ký tự xóa bên phải là N - (i + len).
   • Nếu i + (N - (i + len)) <= k thì hợp lệ.
4. Nếu hợp lệ, kiểm tra xem nó có phải palindrome không (dùng 2 con trỏ).
5. Vì duyệt len giảm dần, xâu đầu tiên tìm thấy sẽ là xâu dài nhất (và theo thứ tự ưu tiên từ trái sang phải).

Phức tạp: Vòng lặp len có O(N), vòng lặp i có O(N), vòng lặp kiểm tra palindrome có O(N). Tổng O(N^3). Nhanh hơn cách 1 một chút vì tránh tạo xâu con mới.

Cách Two Pointers (Tối ưu)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    // Duyệt độ dài xâu con dài nhất có thể
    // Xâu dài nhất có thể là n, ngắn nhất là n - k
    for (int len = n; len >= n - k; len--) {
        // Duyệt số ký tự xóa ở bên trái
        for (int l = 0; l <= k; l++) {
            int r = n - len - l; // Số ký tự xóa ở bên phải
            if (r < 0 || l + r > k) continue;

            // Kiểm tra xâu con s[l ... n - 1 - r]
            int left = l;
            int right = n - 1 - r;
            bool ok = true;

            while (left < right) {
                if (s[left] != s[right]) {
                    ok = false;
                    break;
                }
                left++;
                right--;
            }

            if (ok) {
                cout << s.substr(l, len);
                return 0;
            }
        }
    }
    cout << "No";
}

• Time Complexity: O(K * N)
• Space Complexity: O(1)

Đây là giải thuật tối ưu nhất dựa trên việc kết hợp ý tưởng của hai giải thuật trên.

1. Biến đổi vấn đề: Thay vì duyệt qua các cách xóa, ta duyệt qua độ dài xâu con len mong muốn (từ dài nhất n đến ngắn nhất n - k).
2. Với mỗi độ dài len, ta cần kiểm tra xem có tồn tại xâu con nào độ dài len là palindrome với số ký tự xóa <= k không.
3. Số ký tự xóa tổng cộng là n - len. Gọi l là số xóa bên trái, r là số xóa bên phải. Ta có l + r = n - len.
   • Ta duyệt l từ 0 đến k.
   • Tính r = (n - len) - l. Nếu r < 0 hoặc l + r > k (tức là r > k - l) thì bỏ qua.
   • Thực tế, với len cố định, l chỉ cần chạy từ max(0, n - len - k) đến min(k, n - len). Tuy nhiên, để đơn giản và đảm bảo đúng thứ tự ưu tiên (xóa ít ở bên trái trước), ta có thể duyệt l từ 0 đến k.
4. Với mỗi cặp (l, r) hợp lệ, ta kiểm tra xâu con s[l ... n-1-r] có phải palindrome không. Nếu có, in ra và dừng.

Phức tạp: Độ dài len thay đổi O(N) (hoặc O(K) nếu tối ưu hơn), vòng lặp l chạy O(K), mỗi lần kiểm tra palindrome mất O(N). Tổng O(K * N).

Nếu tối ưu hơn nữa, ta có thể dùng KMP hoặc Hashing để kiểm tra palindrome trong O(1) sau khi tiền xử lý O(N), giảm độ phức tạp xuống O(N) hoặc O(K). Tuy nhiên, với ràng buộc thường thấy của bài này (N <= vài nghìn), O(K * N) là đủ.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vấn đề có thể coi là tìm xâu con liên tiếp dài nhất (và ưu tiên từ trái) sao cho nó là palindrome.
• Số ký tự xóa = N - độ dài xâu con.
• Xâu con hợp lệ phải nằm ở vị trí từ i đến j sao cho i + (N - 1 - j) <= k.
• Vì ưu tiên xóa ký tự ở bên trái (để xâu con bắt đầu sớm nhất) và xâu dài nhất, ta nên duyệt độ dài giảm dần và số ký tự xóa bên trái tăng dần.

Lỗi thường gặp

• Sai lệch trong việc tính toán số ký tự xóa ở hai bên (lỗi off-by-one).
• In ra xâu "No" khi không tìm thấy.
• Xử lý sai trường hợp l + r > k hoặc l + r >= n.
• Độ phức tạp cao (O(N^3)) có thể gây TLE nếu dữ liệu lớn, cần tối ưu kiểm tra palindrome.