Xin chào (HELLO)

Nguồn: NTUCoder Độ khó: Dễ Xâu Dãy con Hai con trỏ

Đề bài

HELLO – Xin chào

Nam là người thích chat với bạn bè trên Internet. Cậu ấy đã lập ra một phòng chat với điều kiện rằng trước khi vào phòng chat, mọi người phải chào hỏi trước.

Một câu chào được định nghĩa rằng, câu chào đó phải là một xâu kí tự, chỉ gồm các chữ cái, không chứa kí tự trắng, sao cho khi xóa đi một số chữ cái, nó sẽ trở thành từ "hello", tất nhiên là sẽ không được phép tráo đổi vị trí các chữ cái, mà chỉ được xóa bớt một số chữ cái.

Ví dụ khi Bình muốn vào phòng chat, Bình gõ "ahhellllloou" thì hệ thống sẽ xem xét xâu này và sẽ tự động loại bỏ các chữ cái để trở thành từ "hello". Như vậy Bình được vào phòng chat.

Nhưng khi Bình gõ "hlelo", hệ thống không thể làm cách nào xóa bớt chữ cái để trở thành từ "hello" được. Như vậy, Bình không được vào phòng chat.

Xác định xem, khi Bình gõ một xâu, xâu đó có được chấp nhận để Bình vào phòng chat hay không?

Dữ liệu nhập: Một dòng chứa xâu chữ cái mà Bình định gõ, với chiều dài từ $1$ đến $100$ chữ cái.

Dữ liệu xuất: Nếu Bình được đồng ý để vào phòng chat, xuất "YES", còn không, xuất "NO" (không chứa dấu ngoặc kép).

Giới hạn: thời gian 1 giây, bộ nhớ 128 MB. Đọc từ bàn phím (standard input), ghi ra màn hình (standard output).

Ví dụ 1 – input

ahhellllloou

Ví dụ 1 – output

YES

Ví dụ 2 – input

hlelo

Ví dụ 2 – output

NO

Ví dụ 3 – input

helhcludoo

Ví dụ 3 – output

YES

Lời mở đầu

Bài này mình được một bạn hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Trước khi vào bài, các bạn nhớ giúp mình chuyện giới hạn thời gian: với các hệ thống chấm bài giới hạn 1 giây, toàn bài chỉ nên lặp cỡ $(3 \div 5) \cdot 10^7$ lần là an toàn, tệ nhất $10^8$ lần (lúc này hên xui). Ngưỡng này là cho C/C++; Python, Java, C# chạy chậm hơn nên ngưỡng phải thấp hơn. Đề cho 2 giây thì nhân ngưỡng lên 2, 100 ms thì chia 10, cứ thế mà tính.

Bài này phải nói là rất dễ: chuỗi dài tối đa có $100$ ký tự, quá nhỏ, làm cách tệ cỡ nào cũng khó mà bị quá thời gian (trừ khi tệ quá mức 😅). Tuy nhiên chưa chắc bạn nào cũng giải được theo cách gọn gàng – mình đã xem code của bạn hỏi bài thì thấy bạn xử lý khá rườm rà, phức tạp. Nên ở đây mình phân tích một cách làm rất gọn, kèm vài kinh nghiệm khi gặp dạng bài kiểu này, các bạn chú ý nha.

Giải thích ví dụ cho bạn nào chưa hiểu đề: với ahhellllloou, ta giữ lại 5 chữ cái tô xanh và xoá hết phần còn lại (không đổi chỗ chữ nào) thì được đúng hello ⇒ YES.

ahhellllloou → YES

ahhellllloou

helhcludoo → YES

helhcludoo

hlelo → NO

hlelo

Xanh = giữ lại, gạch mờ = xoá. Với hlelo: sau chữ e (vị trí 3) chỉ còn đúng một chữ l, không đủ 2 chữ l nên không cách nào xoá ra được hello.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào để nhảy tới:

Cách 1Lật ngược vấn đề: tìm dãy con "hello" bằng một lượt duyệt · O(N)

Cách 1Tìm dãy con "hello" thay vì xoá ký tự – O(N)

Đầu tiên các bạn luôn phải nhớ: với mấy dạng bài kiểu này, đề thường không muốn ta nhìn ra hướng giải thực sự, mà cố tình dẫn ta đi lạc khỏi hướng làm tốt nhất. Thậm chí test ví dụ cũng cố tình đưa ra những trường hợp khiến ta lầm tưởng phải xử lý theo một hướng khác, nên các bạn phải tỉnh táo nhìn kỹ bản chất vấn đề nhé 😉.

Kinh nghiệm: thấy "thêm / xoá phần tử" thì hãy tìm cách né

Chuỗi bản chất là mảng 1 chiều các ký tự. Nếu đề hướng ta tới việc thêm hay xoá phần tử trên mảng, hãy tự hỏi: có cách nào cho ra đúng output mà không cần đụng tới thêm/xoá không? Vì thêm hay xoá một phần tử trên mảng, trường hợp xấu nhất tốn $O(N)$: toàn bộ các phần tử phía sau vị trí đó phải đồng loạt nhích lên hoặc lùi xuống, tạo ra rất nhiều thao tác dịch chuyển. Tránh được thì tốt – vấn đề là phải nhìn ra bản chất để tránh.

Ở bài này, đề định nghĩa: xoá đi một số ký tự (không đổi vị trí các ký tự còn lại) sao cho chuỗi còn lại là hello thì in YES, không xoá được như vậy thì in NO. Bạn nào "ngây thơ", "ngoan ngoãn" làm đúng y như đề mô tả – tức là cố đi xoá ký tự trong chuỗi – là toang ngay: hoặc không làm nổi vì rối, hoặc có làm được thì code cũng dài dòng phức tạp cả về trình bày lẫn hiệu năng 😵.

Ta cần nhìn ra vấn đề thực sự: tại sao phải đi xoá để còn lại hello? Đề đã nói rõ là không thay đổi vị trí các ký tự, chữ nào ở yên chỗ đó. Vậy ta có thể lật ngược vấn đề:

Lật ngược vấn đề

Có tìm được chuỗi con hello trong chuỗi gốc hay không? Các ký tự của nó không cần nằm liên tiếp, có thể rời rạc cách xa nhau, miễn đúng thứ tự: gặp h trước, rồi tới e, rồi l, rồi l, sau cùng là o. Gặp đủ 5 ký tự theo đúng thứ tự đó thì kết luận ngay YES; tới cuối chuỗi vẫn chưa đủ thì kết luận NO. Chỉ cần duyệt từng ký tự của chuỗi gốc, chẳng cần xoá gì cả.

Cụ thể: duyệt chuỗi, gặp ký tự h đầu tiên thì tăng biến đếm lên 1; duyệt tiếp gặp e thì tăng lên 1; gặp l thì tăng 1; gặp l nữa thì tăng 1; cuối cùng gặp o thì tăng 1 nữa. Lúc biến đếm bằng $5$ tức là đủ 5 ký tự đã xuất hiện lần lượt ⇒ in YES và dừng chương trình ngay. Nếu chương trình còn chạy được ra tới ngoài vòng lặp nghĩa là không có tình huống nào thoả YES ⇒ in NO.

Mẹo cho code gọn: duyệt trên chuỗi mẫu

Để khỏi phải viết cả đống if else cho từng chữ h, e, l, l, o, ta tạo chuỗi res = "hello" và biến idx chỉ vào ký tự đang cần tìm trong res, bắt đầu từ $0$. Cứ thấy s[i] == res[idx] thì idx++ để chuyển qua tìm ký tự kế tiếp của res; khi idx == 5 thì kết luận YES. Thực chất đây là kỹ thuật hai con trỏ: i chạy trên chuỗi gốc, idx chạy trên chuỗi mẫu.

Vì sao gặp đúng ký tự cần tìm là "nhận" luôn mà không sợ bỏ lỡ cách chọn tốt hơn? Vì nhận ký tự sớm nhất có thể sẽ để lại phần đuôi chuỗi dài nhất cho các ký tự còn lại – không bao giờ thiệt hơn việc chờ một ký tự giống vậy ở phía sau. Đây là một ý tham lam rất tự nhiên.

Em nhập một chuỗi rồi bấm Tiếp để xem con trỏ i chạy trên chuỗi gốc và con trỏ idx nhích dần trên "hello":

Chuỗi s

Ví dụ nhanh:

Source code để các bạn tham khảo, nhìn vào là thấy rõ tất cả những gì mình đã phân tích ở trên:

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

int main(){
    string s;
    cin >> s;
    string res = "hello";
    int idx = 0;
    for(int i = 0; i < (int)s.length(); ++i){
        if(s[i] == res[idx]){
            idx++;
            if(idx == 5){
                cout << "YES";
                return 0;
            }
        }
    }
    cout << "NO";
    return 0;
}

s = input().strip()
res = "hello"
idx = 0
ok = False
for ch in s:
    if ch == res[idx]:
        idx += 1
        if idx == 5:
            ok = True
            break
print("YES" if ok else "NO")

Bấm Tiếp để chạy tay từng dòng code C++ (phần "Dữ liệu" vẽ chuỗi s với con trỏ i và chuỗi res với con trỏ idx):

C++▶ Chạy tay từng dòng codeDuyệt s một lượt, khớp lần lượt từng ký tự của res = hello, idx = 5 thì in YES.

Dữ liệu vào (stdin) – sửa thoải máiahhellllloou

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 string s;

6 cin >> s;

7 string res = "hello";

8 int idx = 0;

9 for(int i = 0; i < (int)s.length(); ++i){

10 if(s[i] == res[idx]){

11 idx++;

12 if(idx == 5){

13 cout << "YES";

14 return 0;

15 }

16 }

17 }

18 cout << "NO";

19 return 0;

20}

ChậmVừaNhanhRất nhanh

Giải thích 1 số chỗ trong code:

1. (int)s.length(): hàm length() trả về kiểu số nguyên không dấu, ép về int để so sánh với i cho "sạch", không bị trình biên dịch cảnh báo.
2. Ngay khi idx == 5 ta in YES và return 0 luôn: vừa đỡ phải xét tiếp phần còn lại, vừa không bao giờ truy cập res[5] (vượt quá 5 ký tự của "hello").
3. Ra được tới ngoài vòng lặp tức là chưa từng có lúc idx == 5 ⇒ in NO, không cần thêm biến cờ hiệu nào cả.

Đánh giá độ phức tạp của cách làm này:

• Không gian: ngoài chuỗi đầu vào thì chỉ dùng chuỗi res 5 ký tự và vài biến ⇒ $O(1)$.
• Thời gian: duyệt chuỗi đúng 1 lượt ⇒ $O(N)$ với $N$ là độ dài chuỗi đầu vào.

Không gian$O(1)$

Thời gian$O(N)$

Ghi chú của mình: code C++ và Python ở trên cho đúng cả 3 ví dụ của đề, và đã được so với một chương trình vét cạn độc lập (thử mọi bộ 5 vị trí tăng dần xem có ghép ra "hello" không) trên 1100 bộ test ngẫu nhiên độ dài tới 14 (khoảng 340 bộ đáp án YES) – khớp hết. Với chuỗi dài 100 ký tự thì chạy tức thì.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇