Hiểu bài toán

Xâu A được coi là 'tốt' nếu nó có thể được biến đổi từ xâu S ban đầu bằng cách thực hiện một trong hai phép biến đổi sau:

1. Xóa một ký tự.
2. Thay đổi một ký tự 'A' thành 'B' hoặc 'B' thành 'A'.

Yêu cầu: Tìm số lượng xâu 'tốt' có độ dài bằng với xâu S ban đầu (sử dụng phép biến đổi số 2) có giá trị lớn nhất về mặt từ điển (lexicographically largest).

Giải thích chi tiết:

• Xâu 'tốt' là xâu có thể thu được từ S sau một số lượng phép biến đổi (không giới hạn số lần xóa/thay đổi).
• Tuy nhiên, để một xâu T có độ dài bằng S được coi là 'tốt', T phải là một biến thể của S.
• Phép 'thay đổi' (substitution) cho phép biến đổi S thành T.
• Phép 'xóa' (deletion) cho phép loại bỏ các ký tự thừa.
• Vấn đề thực chất là tìm xâu con liên tiếp (substring) của S sao cho:
  1. Xâu con này có thể biến đổi thành một xâu chỉ chứa toàn 'B' (hoặc 'A') bằng cách thay đổi ít hơn hoặc bằng 1 ký tự.
  2. Nếu là xâu con chứa 'B', ta có thể xóa các 'A' ở bên trái để chỉ còn lại dãy 'B'.
  3. Mục tiêu là tìm xâu con dài nhất thỏa mãn điều kiện có thể biến đổi chỉ bằng 1 phép thay đổi.

Đề bài thực chất yêu cầu tìm độ dài của chuỗi 'B' dài nhất hoặc chuỗi 'A' dài nhất có thể tạo được bằng cách xóa các ký tự 'A' (hoặc 'B') thừa và thay đổi tối đa 1 ký tự.

Gợi ý từ các solution:

• Solution 2 (DP): Tính toán chi phí thay đổi để xâu S[0..i] trở thành xâu chỉ chứa 'A' hoặc chỉ chứa 'B'.
• Solution 1 & 3 (Greedy/Duyệt ngược): Duyệt từ phải sang trái, đếm số lượng 'B' liên tiếp. Nếu gặp 'A', kiểm tra xem có thể thay đổi 'A' đó để nối vào dãy 'B' không.

Đề bài gốc (có thể là): Tìm độ dài xâu con dài nhất có thể biến đổi thành xâu toàn 'B' bằng cách thay đổi tối đa 1 ký tự 'A' thành 'B' và xóa các ký tự 'A' ở bên trái.

Thực chất bài này là bài tìm 'Maximum length of a string that can be made all Bs with at most one change'.

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

Cách Quy hoạch động (Dynamic Programming)

#include <bits/stdc++.h>
using namespace std;
int dp[1000009][2];
string s;

int main (){
    freopen("TRANSTR.inp", "r", stdin);
    freopen("TRANSTR.out", "w", stdout);
    cin >> s;
    memset(dp, 0x0f, sizeof dp);
    dp[0][0] = dp[0][1] = 0;
    // 0 la A, 1 la B
    for (int i = 1; i <= s.size(); i ++) {
      if (s[i - 1] == 'A') {
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = min(dp[i - 1][1] + 1, dp[i - 1][0] + 1);
      }
      else {
        dp[i][0] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1);
        dp[i][1] = dp[i - 1][1];
      }
    }
    cout << dp[s.size()][0];
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Cách tiếp cận này sử dụng quy hoạch động để giải bài toán biến đổi xâu.

• dp[i][0]: Chi phí tối thiểu để biến đổi xâu S[0...i-1] thành xâu con chỉ chứa ký tự 'A'.
• dp[i][1]: Chi phí tối thiểu để biến đổi xâu S[0...i-1] thành xâu con chỉ chứa ký tự 'B'.

Logic transitions:

• Nếu S[i-1] == 'A':
  • Để thành xâu 'A' (dp[i][0]): Giữ nguyên 'A', chi phí bằng dp[i-1][0].
  • Để thành xâu 'B' (dp[i][1]): Phải thay đổi 'A' thành 'B', chi phí là min(dp[i-1][1] + 1, dp[i-1][0] + 1) (thêm vào xâu 'B' đang có hoặc chuyển từ xâu 'A').
• Nếu S[i-1] == 'B':
  • Để thành xâu 'A' (dp[i][0]): Phải thay đổi 'B' thành 'A', chi phí là min(dp[i-1][0] + 1, dp[i-1][1] + 1).
  • Để thành xâu 'B' (dp[i][1]): Giữ nguyên 'B', chi phí bằng dp[i-1][1].

Đáp án là dp[n][0] (chi phí để biến toàn bộ xâu thành 'A')? Không, đề bài yêu cầu xâu 'tốt' có giá trị lớn nhất. Nếu chỉ dùng DP này, ta chỉ tính được chi phí. Tuy nhiên, DP này thường dùng để kiểm tra điều kiện.

Lưu ý: Solution 2 in ra dp[s.size()][0]. Nếu bài toán là "Tìm xâu con dài nhất có thể biến đổi thành xâu toàn 'A'", DP này chưa đủ. Có thể solution này giải một biến thể khác hoặc logic code bị thiếu.

Tôi sẽ điều chỉnh giải thích để phù hợp với các solution Greedy (Solution 1 & 3) là chính xác nhất cho bài "Transtr".

Cách Duyệt ngược (Tối ưu)

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("transtr.inp","r",stdin);
    freopen("transtr.out","w",stdout);
    string s;
    cin>>s;
    int size = s.size();
    int res = 0, cnt = 0;
    bool check = true;
    for(int i = size-1;i>=0;i--) {
        if(check) {
            if(s[i] == 'B') {
                ++cnt;
            }
            else {
                if(cnt == 1) {
                    ++res;
                }
                else if(cnt > 1) {
                    ++res;
                    check = false;
                    ++i;
                }
                cnt = 0;
            }
        }
        else {
            if(s[i] == 'A') {
                ++cnt;
            }
            else {
                if(cnt == 1) {
                    ++res;
                }
                else if(cnt > 1) {
                    ++res;
                    check = true;
                    ++i;
                }
                cnt = 0;
            }
        }
    }
    if(cnt) {
        ++res;
    }
    cout<<res;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu nhất, giải quyết trực tiếp bài toán bằng cách duyệt một lần.

Bài toán thực sự: Xâu 'tốt' được tạo thành từ một dãy các ký tự giống nhau (ví dụ 'B') nhưng được phép có tối đa 1 ký tự 'lỗi' (khác loại) ở giữa.

Logic thuật toán:

1. Duyệt xâu từ phải sang trái.
2. Dùng biến check để theo dõi loại ký tự ưu tiên hiện tại (ban đầu là 'B').
3. cnt đếm số lượng ký tự ưu tiên liên tiếp.
4. Khi gặp ký tự khác loại ưu tiên:
   • Nếu cnt == 1: Tức là chỉ có 1 ký tự ưu tiên. Ta có thể thay đổi ký tự đang xét thành ưu tiên để nối dài dãy. res tăng 1, cnt reset.
   • Nếu cnt > 1: Tức là có đoạn dài ký tự ưu tiên. Ta có thể thay đổi 1 ký tự 'lỗi' hiện tại để nối vào dãy. res tăng 1 (đếm dãy trước đó). Sau đó đổi check sang loại ưu tiên mới, và i++ để xét lại ký tự này (nó sẽ là đầu dãy mới).
5. Cuối cùng, nếu còn cnt > 0, cộng dồn vào res.

Ví dụ: BBAB

• i=3 ('B'): check=true, cnt=1.
• i=2 ('A'): check=true, cnt=0. Gặp 'A', cnt trước đó là 1 -> res=1. check=false (bắt đầu tìm dãy A). Nhảy lại i=2.
• i=2 ('A'): check=false, cnt=1.
• i=1 ('B'): check=false, cnt=0. Gặp 'B', cnt trước đó là 1 -> res=2. check=true. Nhảy lại i=1.
• i=1 ('B'): check=true, cnt=1.
• i=0 ('B'): check=true, cnt=2.
• Hết loop. cnt > 0 -> res = 3.

Kết quả là 3 (ví dụ xâu BBBB sau khi xử lý).

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

Bài học kinh nghiệm

• Bài toán có thể được chia thành các 'khối' chứa ký tự giống nhau, được ngăn cách bởi các ký tự đơn (điểm thay đổi).
• Việc duyệt từ phải sang trái giúp dễ dàng xác định xem một ký tự 'lỗi' có thể được 'sử dụng' để thay đổi hay không dựa trên độ dài của dãy ký tự ưu tiên ở bên phải.
• Số lượng phép thay đổi tối đa là 1, vì vậy thuật toán chỉ cần xử lý các trường hợp dãy ưu tiên có độ dài >= 2 hoặc <= 1 để quyết định có 'nuốt' ký tự lỗi hay không.

Lỗi thường gặp

• Quên xử lý dãy còn sót lại sau khi vòng lặp kết thúc (trong code mẫu có if(cnt) ++res;).
• Lỗi index khi sử dụng ++i để lùi lại bước xét (cần phải đảm bảo index không tràn).
• Nhầm lẫn giữa việc thay đổi ký tự hiện tại và việc bỏ qua ký tự hiện tại.