Đoạn lặp dài nhất trong chuỗi ADN (CSES 1069)

Nguồn: CSES Problem Set Độ khó: Dễ Chuỗi CSES 1069

Đề bài

Một chuỗi ADN được viết dưới dạng xâu chỉ gồm bốn chữ cái in hoa A, C, G, T.

Hãy tìm độ dài lớn nhất của một đoạn liên tiếp trong xâu mà mọi ký tự trong đoạn đều giống nhau.

Dữ liệu vào:

Một dòng chứa xâu $s$ (chỉ gồm các ký tự A, C, G, T).

Kết quả:

In ra một số nguyên là độ dài đoạn liên tiếp dài nhất gồm toàn một loại ký tự.

Giới hạn:

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

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

Ví dụ 1 – input

GTTTACCA

Ví dụ 1 – output

3

Giải thích:

Các đoạn gồm cùng một ký tự là G, TTT, A, CC, A. Đoạn dài nhất là TTT có độ dài $3$.

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

Bài gốc tiếng Anh

Đề gốc trên CSES Problem Set, em cũng có thể nộp thử ở đó.

Mở bài trên CSES

Ý tưởng

Duyệt xâu từ trái sang phải, giữ dai = độ dài đoạn cùng ký tự kết thúc tại vị trí hiện tại:

• nếu s[i] == s[i-1] thì dai++;
• ngược lại một đoạn mới bắt đầu, dai = 1.

Sau mỗi bước cập nhật tot = max(tot, dai). Ban đầu tot = dai = 1 (xâu có ít nhất một ký tự).

Chạy tay với GTTTACCA: dai lần lượt 1, 1, 2, 3, 1, 1, 2, 1 → tot = 3.

Lưu ý / bẫy thường gặp

• Chỉ cập nhật tot khi gặp ký tự khác → quên đoạn cuối xâu (ví dụ ACGTTTTT).
• Đặt lại dai = 0 thay vì 1 khi sang đoạn mới.
• Đếm số lần xuất hiện của từng ký tự – đề hỏi đoạn liên tiếp, không phải tần suất (ACACACAA đáp án là 2, không phải 5).
• Từ mỗi vị trí lại đếm lại cả đoạn → $O(n^2)$ khi xâu toàn một ký tự.

Lời giải

Code chuẩn bên dưới đã chấm đúng toàn bộ 20 test trên CLUE OJ.

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 😇