Đếm số lần xuất hiện của từng chữ cái

Nguồn: CLUE OJ Độ khó: Dễ Xâu Mảng đếm

Đề bài

Với xâu BANNA ta đếm được có $2$ kí tự A, $1$ kí tự B và $2$ kí tự N.

Em hãy lập trình nhập vào một xâu chỉ gồm các chữ cái in hoa, đếm và in ra số lần xuất hiện của từng chữ cái có mặt trong xâu.

Dữ liệu vào:

Một dòng là xâu $S$ chỉ gồm các chữ cái in hoa từ A đến Z.

Kết quả:

Với mỗi chữ cái có xuất hiện trong $S$, in một dòng gồm chữ cái đó, một dấu cách và số lần xuất hiện của nó. Các dòng in theo thứ tự từ điển (từ A đến Z); chữ cái không xuất hiện thì không in.

Giới hạn:

• $1 \le |S| \le 10^6$

Subtask:

• Subtask 1 (40% số điểm): $|S| \le 1000$.
• Subtask 2 (60% số điểm): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

ABABBCH

Ví dụ 1 – output

A 2
B 3
C 1
H 1

Nguồn: phỏng theo bài "ĐẾM KÍ TỰ" – vinhdinhcoder.net (chủ đề Xâu kí tự).

Lời mở đầu

Đếm xem mỗi chữ cái xuất hiện bao nhiêu lần trong một xâu dài tới $10^6$ kí tự. Cách "với mỗi vị trí, đi đếm lại cả xâu" mất $10^{12}$ bước. Ta chỉ cần 26 cái hộp đếm – một mảng dem[26] – và duyệt xâu đúng một lần. Ghi chú: ví dụ trong lời đề gốc là "BAN NA" (có dấu cách) nhưng đề lại nói xâu chỉ gồm chữ hoa; mình chốt xâu chỉ gồm chữ cái in hoa A–Z, không có dấu cách.

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:

Bộ test20 testÝ tưởngmảng đếm 26 ôLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Test 1–8 là xâu ngắn, test 9–20 là xâu dài tới $10^6$ kí tự.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2, 6, 8	Thứ tự xuất hiện khác thứ tự từ điển – in theo thứ tự xuất hiện là sai
3–4, 7, 10–11	Có chữ Z – vòng lặp c < 'Z' bỏ sót
5, 11, 20	Chỉ một loại chữ cái – không được in các chữ có 0 lần
9–20	Xâu dài tới $10^6$ – đếm lại cả xâu cho mỗi vị trí bị quá thời gian

Ý tưởngMảng đếm: ô thứ c đếm chữ cái thứ c

Chữ cái ch ứng với ô số ch - 'A' (từ 0 tới 25). Duyệt xâu một lần, gặp ch thì dem[ch - 'A']++.

Sau đó duyệt $c$ từ 0 tới 25 – tức là đúng thứ tự từ điển – và chỉ in những ô có dem[c] > 0. Chữ cái tương ứng là char('A' + c).

Vì sao nhanh?

Mỗi kí tự chỉ làm một phép tăng, tổng cộng $|S| + 26$ bước. Cách "với mỗi vị trí $i$, đếm lại xem s[i] xuất hiện bao nhiêu lần" mất $|S|^2 = 10^{12}$ bước.

Em nhập xâu chữ in hoa rồi bấm Tiếp để xem các hộp đếm tăng dần:

s =

Ví dụ nhanh:

Lời giảiĐếm một lần, in theo thứ tự ô

Khai báo int dem[26] = {0}; để mọi ô bắt đầu từ 0.

C++▶ Chạy tay từng dòng codeTăng ô dem[s[i] - 'A'], rồi in các ô khác 0.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Mô phỏng chỉ dừng ở các ô có giá trị khác 0 cho gọn; chương trình thật vẫn xét đủ 26 ô.

1. s[i] - 'A' biến chữ cái thành chỉ số 0..25; char('A' + c) làm ngược lại.
2. Duyệt c từ 0 tới 25 (dùng c < 26, hay c <= 'Z' nếu duyệt bằng kí tự) để không bỏ sót chữ Z.
3. Bản Python dùng danh sách [0] * 26 và ord(c) - ord('A').

Không gian$O(26)$

Thời gian$O(|S| + 26)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.029s. Bản Python đúng 20/20 test, chạy lâu nhất 0.185s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
In cả những chữ cái xuất hiện 0 lần	6/20	sai test 1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 14, 15, 17, 20
In theo thứ tự xuất hiện trong xâu	6/20	sai test 2, 4, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18
Với mỗi vị trí, đếm lại cả xâu	9/20	sai test 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20
Vòng lặp for (c = 'A'; c < 'Z'; c++)	6/20	sai test 3, 4, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.029s	Full điểm
	Python	20/20	0.185s	Full điểm
In cả ô 0	C++	6/20	–	Mất 14 test
Thứ tự xuất hiện	C++	6/20	–	Mất 14 test
Đếm lại cả xâu	C++	9/20	–	Mất 11 test
Thiếu chữ Z	C++	6/20	–	Mất 14 test

Ghi chú của mình: mảng đếm theo chữ cái (dem[26]) là công cụ số 1 của chương xâu: kiểm tra hai xâu là hoán vị của nhau, tìm chữ xuất hiện nhiều nhất, xâu có tạo thành đối xứng được không…

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 😇