Hiểu bài toán

Bài toán yêu cầu khôi phục lại chuỗi ban đầu từ chuỗi đã được mã hóa theo quy tắc: tất cả các ký tự nguyên âm ('a', 'e', 'i', 'o', 'u') trong chuỗi ban đầu bị nhân đôi. Do đó, trong chuỗi mã hóa, mỗi nguyên âm sẽ xuất hiện chính xác 2 lần liên tiếp. Nhiệm vụ là duyệt qua chuỗi mã hóa và chỉ giữ lại một ký tự cho mỗi cặp nguyên âm đôi, trong khi giữ nguyên các ký tự còn lại (bao gồm phụ âm và khoảng trắng).

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

Cách Duyệt tuần tự và bỏ qua ký tự thừa

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

bool isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int n;
        string s;
        cin >> n;
        cin.ignore();
        getline(cin, s);

        string result;
        for (int i = 0; i < s.size(); i++) {
            result += s[i];
            if (isVowel(s[i]) && i + 1 < s.size() && s[i + 1] == s[i]) {
                i++;
            }
        }

        cout << "Case #" << t << ": " << result << "\n";
    }

    return 0;
}

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

Hàm isVowel kiểm tra xem một ký tự có phải là nguyên âm hay không. Trong vòng lặp chính, ta duyệt qua chuỗi s. Với mỗi ký tự tại vị trí i, ta thêm nó vào chuỗi kết quả result. Sau đó, ta kiểm tra điều kiện: nếu ký tự hiện tại là nguyên âm và nó giống với ký tự tiếp theo, điều đó có nghĩa là chúng là một cặp đôi trong chuỗi mã hóa. Do đó, ta cần bỏ qua ký tự tiếp theo bằng cách tăng chỉ số i lên 1 (lưu ý vòng lặp cũng sẽ tăng i sau mỗi lần lặp). Phương pháp này xử lý trực tiếp và loại bỏ các ký tự thừa ngay khi phát hiện.

Cách Xử lý dựa trên so sánh ký tự kế tiếp

#include <iostream>

using namespace std;

int isVowel(char c) {
    if (c == 'a' || c == 'e' || c == 'o' || c == 'u' || c == 'i') return 1;
    return 0;
}

int main() {
    int t;
    cin >> t;

    for (int k = 1; k <= t; ++k) {
        int len;
        cin >> len;
        char *s = new char[len+1];
        cin.ignore();
        cin.getline(s, len+1);
        char *ans = new char[len+1];

        int pos = -1;

        for (int i = 0; i < len; ++i) {
            if (i == len-1) {
                ++pos; ans[pos] = s[i];
                continue;
            }
            if (s[i] == s[i+1] && isVowel(s[i])) {
                ++pos;
                ans[pos] = s[i];
                ++i;
                continue;
            }
            ++pos;
            ans[pos] = s[i];
        }

        ans[++pos] = '\0';

        cout << "Case #" << k << ": " << ans << "\n";

        delete[] s;
        delete[] ans;
    }

    return 0;
}

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

Cách tiếp cận này sử dụng mảng ký tự (C-style string) thay vì std::string. Nó duyệt qua chuỗi đầu vào s và xây dựng chuỗi ans. Logic cơ bản tương tự như Approach 1: nếu phát hiện một cặp ký tự giống nhau là nguyên âm, ta chỉ thêm một ký tự vào ans và tăng chỉ số i thêm 1 để bỏ qua ký tự thứ hai. Nếu không phải là cặp nguyên âm, ta thêm ký tự hiện tại và tiếp tục. Cách này làm nổi bật việc quản lý bộ nhớ thủ công trong C++.

Cách Sử dụng map để kiểm tra nguyên âm

#include<bits/stdc++.h>
#define el '\n'
#define ll long long
#define N 1000000
using namespace std;
ll t,n;
string s;
map<char,ll> m;
int main(){
         ios_base::sync_with_stdio(false);
         cin.tie(NULL);cout.tie(NULL);
         m['u']=1;
         m['e']=1;
         m['o']=1;
         m['a']=1;
         m['i']=1;
         cin>>t;
         cin.ignore();
         for(ll x=1;x<=t;x++){
            cin>>n;
         cin.ignore();
            getline(cin,s); string k="";
            ll i=0;
            while(i<s.size()){
                if(m[s[i]]==1 && s[i]==s[i+1]) {k+=s[i];i=i+2;}
                else {k+=s[i];i++;}
            }
            cout << "Case" << " " << "#"  << x << ":" << " " << k << el;
         }
}

• Time Complexity: O(N log K)
• Space Complexity: O(N)

Phương pháp này cũng sử dụng thuật toán duyệt và loại bỏ ký tự thừa tương tự như các cách trên. Điểm khác biệt nằm ở việc kiểm tra nguyên âm: tác giả sử dụng một std::map<char, ll> để lưu trữ các nguyên âm và tra cứu. Trong khi các cách khác sử dụng hàm if lồng nhau hoặc switch, cách dùng map này linh hoạt hơn nếu bảng ký tự thay đổi, nhưng về hiệu năng thì chậm hơn do chi phí truy cập map là O(log K) (với K là số lượng nguyên âm, ở đây là 5).

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

Bài học kinh nghiệm

• Quy tắc mã hóa là cố định: mỗi nguyên âm trong từ điển gốc sinh ra 2 nguyên âm giống nhau trong chuỗi mã hóa.
• Bài toán có thể được giải quyết bằng cách duyệt một chiều chuỗi (Single Pass) với độ phức tạp tuyến tính O(N).
• Cần phân biệt rõ ràng giữa việc 'đọc' một ký tự và 'bỏ qua' một ký tự.

Lỗi thường gặp

• Truy cập chỉ số ngoài biên mảng (trên s[i+1]) khi i đang ở phần tử cuối cùng của chuỗi. Cần kiểm tra điều kiện i + 1 < s.size() trước khi so sánh.
• Quên xử lý các ký tự không phải nguyên âm (phụ âm, khoảng trắng) hoặc xử lý sai việc giữ lại các ký tự này.
• Đọc sai yêu cầu Input/Output: Ví dụ in sai format (Case #1: thay vì Case #1: ), hoặc không xử lý đúng việc đọc chuỗi có chứa khoảng trắng (dùng cin >> s thay vì getline).