Đếm Ký Tự (HSG9 TP Đà Nẵng 2018-2019 – Bài 1)

Nguồn: HSG9 TP Đà Nẵng 2018-2019 Độ khó: Dễ Xử lý xâu Đếm Sắp xếp

Đề bài

Câu 1. Đếm ký tự (3 điểm) – Kì thi chọn học sinh giỏi lớp 9 cấp thành phố, TP Đà Nẵng, năm học 2018-2019.

Viết chương trình thực hiện: Nhập vào từ bàn phím một xâu kí tự $S$ (không chứa kí tự dấu cách và có không quá 255 kí tự) và in ra màn hình số lượng các kí tự chỉ xuất hiện đúng 1 lần trong xâu $S$.

Dữ liệu vào: một dòng duy nhất là xâu $S$ (không chứa dấu cách, độ dài không quá 255).

Kết quả: một số nguyên là số lượng các kí tự chỉ xuất hiện đúng 1 lần trong $S$.

Giới hạn thời gian trên hệ thống chấm: 1 giây.

Ví dụ – input

abbacdmedc

Ví dụ – output

2

Giải thích: Trong xâu kí tự được nhập từ bàn phím có 2 kí tự là m và e chỉ xuất hiện đúng 1 lần.

Lời mở đầu

Bài này nằm trong đề thi học sinh giỏi tin học lớp 9 thành phố Đà Nẵng, mình được một bạn học viê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 điều này: với các hệ thống chấm giới hạn 1 giây, toàn bài chỉ nên lặp khoảng $(3 \to 5) \cdot 10^7$ lần là an toàn, tệ nhất là $10^8$ (lúc này hên xui). Đề cho 2 giây thì nhân 2 ngưỡng lên, 100 ms thì chia 10. Ngưỡng này là cho C/C++, còn Python, C#, Java chạy chậm hơn nên ngưỡng phải thấp hơn nữa nha.

Giải thích ví dụ một chút: xâu abbacdmedc có số lần xuất hiện của từng kí tự như sau, chỉ m và e xuất hiện đúng 1 lần nên đáp án là 2.

Kí tự	a	b	c	d	e	m
Số lần	2	2	2	2	1	1

Đề trông đơn giản nhưng dễ sai

Nhiều bạn nhìn test ví dụ rồi dùng mảng đánh dấu 26 phần tử cho 26 chữ cái a…z. Coi chừng sai nhé! Đề chỉ nói xâu $S$ không có dấu cách, chứ không hề nói chỉ gồm chữ cái thường. Xâu hoàn toàn có thể có chữ in hoa A, B, C, chữ số, hay các kí tự lạ như @ ! $ % & *… Dù bạn có nộp AC trên trang web thì cũng chưa chắc đúng, vì bộ test trên web là do admin tự làm chứ không phải bộ test chính thức của Sở Giáo dục.

Với độ dài tối đa chỉ 255 kí tự thì dù thuật toán tệ cỡ nào cũng khó mà TLE được (trừ khi phải tệ lắm lắm hihi). Nên ở bài gốc, chủ yếu là làm sao ra đáp án đúng. Còn trong bài viết này mình sẽ nâng độ khó lên: giả sử xâu dài tới $10^6$ kí tự thì sao?

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 từng phần để nhảy tới:

Cách 1Vét cạn O(N²) · đủ cho N ≤ 255Cách 2Sắp xếp + xét hàng xóm O(N log N)

Cách 1Vét cạn – O(N²)

Tư tưởng đơn giản nhất là vét cạn: với mỗi kí tự $s[i]$, ta so sánh nó với toàn bộ các kí tự trong xâu (kể cả với chính nó). Mỗi lần trùng thì tăng biến đếm cnt. Sau cùng nếu cnt == 1 tức là $s[i]$ chỉ trùng với chính nó, không trùng với kí tự nào khác ⇒ nó được tính vào đáp án. Đếm xem có bao nhiêu kí tự như vậy là xong.

Nhập xâu bằng cin hay getline?

Đề đã nói xâu không có khoảng trắng nên ta dùng cin >> s được. Còn nếu đề không có ràng buộc đó (xâu có thể có dấu cách) thì không được dùng cin >>, vì nó dừng lại khi gặp khoảng trắng nên có thể đọc chưa hết xâu. Lúc đó phải dùng getline(cin, s); nha.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main() {
    string s;
    cin >> s;
    int res = 0;
    for(int i = 0; i < (int)s.length(); ++i){
        int cnt = 0;
        for(int j = 0; j < (int)s.length(); ++j){
            if(s[i] == s[j]){
                cnt++;
            }
        }
        if(cnt == 1){
            res++;
        }
    }
    cout << res;
    return 0;
}

s = input().strip()
res = 0
for i in range(len(s)):
    cnt = 0
    for j in range(len(s)):
        if s[i] == s[j]:
            cnt += 1
    if cnt == 1:
        res += 1
print(res)

C++▶ Chạy tay từng dòng codeCách 1: với mỗi s[i], đếm số kí tự bằng nó trong cả xâu; cnt == 1 thì tính vào res.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main() {

5 string s;

6 cin >> s;

7 int res = 0;

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

9 int cnt = 0;

10 for(int j = 0; j < (int)s.length(); ++j){

11 if(s[i] == s[j]){

12 cnt++;

13 }

14 }

15 if(cnt == 1){

16 res++;

17 }

18 }

19 cout << res;

20 return 0;

21}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(N)$ với $N$ là độ dài xâu $s$.
• Thời gian: $O(N)$ cho bước nhập xâu + $O(N^2)$ cho bước xử lý chính (hai vòng lặp lồng nhau). Theo quy tắc cộng BigO ta lấy thành phần lớn nhất ⇒ $O(N^2)$. (Dấu ^ ở đây là lũy thừa nha, không phải phép xor.)

Không gian$O(N)$

Thời gian$O(N^2)$

Với $N$ tối đa 255 thì $255^2 = 65\,025$ phép so sánh, quá nhỏ so với ngưỡng $(3 \to 5) \cdot 10^7$, nên dù là cách tệ nhất này cũng không thể TLE được.

Trong phòng thi thì sao?

Thực ra đến đây là xong rồi đó các bạn. Nếu đang trong phòng thi mà gặp đúng bài này thì là mình, mình cũng làm đúng cách ở trên thôi: giới hạn quá nhỏ nên chủ yếu ra đáp án đúng, chọn cách đơn giản nhất, nhẹ đầu và nhanh gọn để code, dành thời gian làm bài khác hehe.

Nhưng giờ giả sử xâu dài tới $10^6$ kí tự. Lúc đó $(10^6)^2 = 10^{12}$, vượt quá xa ngưỡng cho phép ⇒ cách này chắc chắn TLE. Phải tìm cách khác tốt hơn.

Luôn có một bản vét cạn trong tay

Với mọi bài, nếu chưa nghĩ ra cách tối ưu (hoặc nghĩ ra nhưng chưa chắc đúng) thì hãy code vét cạn trước. Vét cạn chạy lâu nhưng dễ cài đúng, nên ta dùng nó để kiểm tra cách tối ưu bằng test ngẫu nhiên. Làm vét cạn rồi thì các bạn cũng dễ nhìn ra chỗ dở của nó để tối ưu. Còn nếu cuối cùng vẫn không nghĩ ra cách tốt hơn thì vét cạn cũng giúp các bạn vét được bao nhiêu điểm thì vét (với thể thức chấm IOI – đúng test nào có điểm test đó).

Cách 2Sắp xếp rồi xét hai hàng xóm – O(N log N)

Cách 1 dở ở chỗ: với mỗi $s[i]$ phải duyệt hết cả xâu mới biết có bao nhiêu kí tự trùng với nó. Lý do phải duyệt hết là vì các kí tự đang nằm lộn xộn. Vậy nếu ta gom các kí tự giống nhau nằm sát cạnh nhau thì để biết một kí tự xuất hiện mấy lần chỉ cần nhìn các vị trí lân cận thôi, các bạn đồng ý không?

Muốn vậy thì chỉ cần sắp xếp xâu tăng dần (theo mã ASCII): các kí tự giống nhau sẽ nằm liền một cụm. Khi đó kí tự $s[i]$ xuất hiện đúng 1 lần khi và chỉ khi nó khác cả hàng xóm bên trái $s[i-1]$ lẫn hàng xóm bên phải $s[i+1]$.

Ý chính

Sau khi sort: $s[i]$ chỉ xuất hiện 1 lần $\iff$ ($i = 0$ hoặc $s[i-1] \ne s[i]$) và ($i = N-1$ hoặc $s[i+1] \ne s[i]$).

Coi chừng hai đầu xâu

Kí tự ở index $0$ không có hàng xóm bên trái, kí tự ở index $N-1$ không có hàng xóm bên phải. Phải đặt điều kiện i - 1 >= 0 và i + 1 < s.length() trước khi truy cập, tránh truy cập ra ngoài xâu.

Minh hoạ sắp xếp và xét hàng xóm

Em nhập xâu bất kì (không dấu cách) rồi bấm Tiếp để xem xâu được sắp xếp, rồi từng kí tự được so với hai hàng xóm như thế nào:

Xâu S

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main() {
    string s;
    cin >> s;
    int res = 0;
    sort(s.begin(), s.end());
    for(int i = 0; i < (int)s.length(); ++i){
        bool check = true;
        if(i - 1 >= 0 && s[i - 1] == s[i]){
            check = false;
        }
        if(i + 1 < (int)s.length() && s[i + 1] == s[i]){
            check = false;
        }
        if(check == true){
            res++;
        }
    }
    cout << res;
    return 0;
}

s = sorted(input().strip())
n = len(s)
res = 0
for i in range(n):
    check = True
    if i - 1 >= 0 and s[i - 1] == s[i]:
        check = False
    if i + 1 < n and s[i + 1] == s[i]:
        check = False
    if check:
        res += 1
print(res)

C++▶ Chạy tay từng dòng codeCách 2: sort xâu, kí tự khác cả hai hàng xóm thì chỉ xuất hiện 1 lần.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main() {

5 string s;

6 cin >> s;

7 int res = 0;

8 sort(s.begin(), s.end());

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

10 bool check = true;

11 if(i - 1 >= 0 && s[i - 1] == s[i]){

12 check = false;

13 }

14 if(i + 1 < (int)s.length() && s[i + 1] == s[i]){

15 check = false;

16 }

17 if(check == true){

18 res++;

19 }

20 }

21 cout << res;

22 return 0;

23}

ChậmVừaNhanhRất nhanh

Giải thích một số chỗ trong code:

• sort(s.begin(), s.end()); sắp xếp xâu $s$ tăng dần. Hàm này nằm trong thư viện <algorithm>; mình include <bits/stdc++.h> là bao hết rồi, còn bạn nào không dùng thì nhớ #include <algorithm> nha.
• Biến cờ hiệu check mặc định là true (hợp lệ), sau đó xét các tình huống làm nó không hợp lệ để gán false. Cuối cùng nếu vẫn true thì $s[i]$ chỉ xuất hiện 1 lần và được tính vào kết quả.
• Hai trường hợp gán check = false là 2 cái if riêng, không phải if … else if. Vì đó là 2 trường hợp riêng lẻ, phải xét đồng thời cả 2; dùng else if là chỉ xét 1 trong 2 thì không đúng.
• Chỗ if(check == true){ res++; } mình cố tình viết rõ ra, chứ bình thường mình sẽ viết res += check;. Trong C/C++ true là 1, false là 0, nên cộng thẳng check vào res là y chang.

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

• Không gian: $O(N)$ với $N$ là độ dài xâu $s$.
• Thời gian: $O(N)$ nhập xâu + $O(N \log N)$ sắp xếp + $O(N)$ duyệt đếm ⇒ tổng quát $O(N \log N)$. Với $N = 10^6$: khoảng $10^6 \cdot 20 = 2 \cdot 10^7$, vẫn trong ngưỡng an toàn.

Không gian$O(N)$

Thời gian$O(N \log N)$

Dùng hàm sort có sẵn

Hàm sort của C++ luôn đảm bảo $O(N \log N)$ (nó kết hợp nhiều thuật toán sắp xếp tối ưu bên trong). Tự cài Quick Sort, Merge Sort, Heap Sort thì mất công hơn, lỡ cài sai, hoặc Quick Sort rơi vào trường hợp xấu nhất cũng thành $O(N^2)$. Còn nếu cài Interchange Sort, Selection Sort, Bubble Sort… thì là $O(N^2)$, ngang với cách 1 ⇒ chắc chắn TLE khi $N = 10^6$.

Đến đây các bạn đã thấy cái hay của giải thuật rồi chứ? Từ $O(N^2)$ xuống $O(N \log N)$: với $N = 255$ là từ $65\,025$ xuống khoảng $2\,040$; với $N = 10^6$ là từ $10^{12}$ (1000 tỷ) xuống $2 \cdot 10^7$ (20 triệu). Cứ tưởng tượng khoản nợ 1000 tỷ giờ giảm còn 20 triệu là thấy nó bớt cỡ nào hehe 😆.

Nếu đề chỉ có chữ cái a – z

Nếu đề ràng buộc thêm là xâu chỉ gồm chữ cái thường a…z thì ta dùng mảng đánh dấu 26 phần tử như nói lúc đầu: duyệt xâu 1 lần để thống kê, rồi duyệt lại mảng đánh dấu là xong, độ phức tạp chỉ $O(N)$.

Mở rộng thêm một chút

Thật ra kiểu char trong C++ chỉ chiếm 1 byte, tức là chỉ có tối đa 256 giá trị khác nhau. Nên kể cả khi xâu có kí tự bất kì, ta vẫn dùng được mảng đánh dấu 256 phần tử (không phải 26) để đạt $O(N)$: int cnt[256] = {0}; for(char c : s) cnt[(unsigned char)c]++; rồi đếm các x có cnt[x] == 1. Ép sang unsigned char để chỉ số không bị âm với các byte lớn hơn 127.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 500 bộ test ngẫu nhiên (xâu dài tới 255 kí tự, gồm đủ loại kí tự ASCII in được: chữ hoa, chữ thường, chữ số, kí hiệu), so với code đếm bằng Counter – khớp hết (đoạn mảng đánh dấu 256 phần tử ở trên cũng được thử với 200 bộ, khớp hết). Với xâu $10^6$ kí tự, cách 2 (C++) chạy khoảng 0.1 giây.

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 😇