Hiểu bài toán

Bài toán yêu cầu kiểm tra xem một xâu S có chứa xâu "hello" như một subsequence hay không. Subsequence ở đây nghĩa là ta có thể xóa một số ký tự (có thể không xóa ký tự nào) từ S để thu được xâu "hello", trong đó các ký tự của "hello" phải xuất hiện trong S theo đúng thứ tự, nhưng không nhất thiết phải liên tiếp nhau.

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

Cách Duyệt tuần tự (Two Pointers / Greedy)

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    string t = "hello";
    int j = 0;

    // Duyệt qua từng ký tự của xâu nhập vào
    for (char c : s) {
        // Nếu ký tự hiện tại trùng với ký tự cần tìm tiếp theo của "hello"
        if (c == t[j]) {
            j++;
        }
        // Nếu đã tìm thấy đủ "hello"
        if (j == 5) break;
    }

    if (j == 5) cout << "YES";
    else cout << "NO";

    return 0;
}

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

Đây là cách tiếp cận trực quan và hiệu quả nhất. Ta sử dụng một chỉ số (con trỏ) j để theo dõi vị trí hiện tại của ta trong xâu "hello". Ta duyệt qua từng ký tự của xâu S. Nếu ký tự hiện tại khớp với ký tự t[j] mà ta đang cần tìm, ta di chuyển j sang phải (tức là đã tìm thấy ký tự đó). Nếu j bằng độ dài của "hello" (tức là 5), điều đó có nghĩa ta đã tìm thấy đủ chuỗi con mong muốn. Nếu duyệt hết S mà j chưa bằng 5, nghĩa là không đủ.

Cách Tìm kiếm vị trí (String Find)

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    string p = "hello";
    int pos = -1;
    bool valid = true;

    // Duyệt qua từng ký tự của "hello"
    for (char c : p) {
        // Tìm ký tự c trong s bắt đầu từ vị trí pos + 1
        pos = s.find(c, pos + 1);
        if (pos == string::npos) {
            valid = false;
            break;
        }
    }

    if (valid) cout << "YES";
    else cout << "NO";

    return 0;
}

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

Phương pháp này sử dụng hàm find của thư viện chuẩn. Ta duy trì một biến pos lưu vị trí tìm thấy cuối cùng. Với mỗi ký tự trong "hello", ta tìm kiếm nó trong S từ sau vị trí pos trước đó. Nếu tìm thấy, ta cập nhật pos. Nếu không tìm thấy bất kỳ ký tự nào, ta dừng lại và kết luận 'NO'.

Cách Quay lui (Backtracking)

#include <iostream>
#include <string>
using namespace std;

bool isSubsequence(int s_idx, int t_idx, string& s, string& t) {
    // Nếu đã tìm thấy hết "hello"
    if (t_idx == 5) return true;
    // Nếu duyệt hết S mà chưa tìm thấy hết "hello"
    if (s_idx == s.length()) return false;

    // Nếu ký tự hiện tại khớp, thử chọn nó hoặc không chọn nó
    if (s[s_idx] == t[t_idx]) {
        if (isSubsequence(s_idx + 1, t_idx + 1, s, t)) return true;
    }

    // Thử bỏ qua ký tự hiện tại
    return isSubsequence(s_idx + 1, t_idx, s, t);
}

int main() {
    string s;
    cin >> s;
    string t = "hello";

    if (isSubsequence(0, 0, s, t)) cout << "YES";
    else cout << "NO";

    return 0;
}

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

Đây là cách tiếp cận theo đệ quy (quay lui). Hàm isSubsequence thử tất cả các cách để tạo ra xâu "hello". Nó có hai lựa chọn ở mỗi bước: hoặc là sử dụng ký tự hiện tại của S nếu nó khớp với ký tự cần trong "hello", hoặc là bỏ qua nó. Mặc dù đúng về mặt logic, nhưng độ phức tạp là quá lớn (2^n) so với ràng buộc n=100, dẫn đến thời gian chạy lâu hoặc lỗi quá tải (Time Limit Exceeded).

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

Bài học kinh nghiệm

• Bài toán chỉ yêu cầu kiểm tra sự tồn tại của xâu 'hello' theo thứ tự, không cần các ký tự này liên tiếp nhau.
• Cách tiếp cận Greedy (duyệt một lần từ trái sang phải) là tối ưu nhất về cả thời gian và bộ nhớ.
• Vì độ dài xâu 'hello' cố định và rất ngắn (5), ta không cần các thuật toán phức tạp như Quay lui hay Quy hoạch động.

Lỗi thường gặp

• Nhầm lẫn giữa 'subsequence' (xâu con theo thứ tự) và 'substring' (xâu con liên tiếp). Nếu bài toán yêu cầu substring, ta chỉ cần dùng hàm find một lần. Nhưng ở đây ta cần kiểm tra theo thứ tự.
• Sử dụng đệ quy quá sâu hoặc thuật toán không hiệu quả có thể gây tràn bộ nhớ hoặc quá thời gian chạy.
• Quên kiểm tra điều kiện dừng sớm (break) khi đã tìm thấy đủ xâu 'hello' để tối ưu hóa.