Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

---

Bài toán được chuyển sang dạng nhập/xuất chuẩn (stdin/stdout); định dạng xem ở mục Dữ liệu vào.

LeetCode 2024 – Maximize the Confusion of an Exam (Làm rối đề thi nhiều nhất) – độ khó Medium.

Một thầy giáo đang soạn một bài kiểm tra gồm ~n~ câu hỏi đúng/sai, trong đó 'T' nghĩa là đúng (true) và 'F' nghĩa là sai (false). Thầy muốn làm học sinh bối rối bằng cách làm cho số câu hỏi liên tiếp có cùng đáp án (nhiều câu đúng liên tiếp hoặc nhiều câu sai liên tiếp) là lớn nhất.

Cho xâu answerKey, trong đó answerKey[i] là đáp án ban đầu của câu hỏi thứ ~i~. Ngoài ra cho số nguyên ~k~ – số lần tối đa được thực hiện thao tác sau:

• Đổi đáp án của một câu hỏi bất kỳ thành 'T' hoặc 'F' (tức là gán answerKey[i] bằng 'T' hoặc 'F').

Yêu cầu: trả về số lượng lớn nhất các ký tự 'T' liên tiếp hoặc các ký tự 'F' liên tiếp trong xâu đáp án sau khi thực hiện thao tác không quá ~k~ lần.

Dữ liệu vào

• Dòng đầu là xâu answerKey.
• Dòng thứ hai là số nguyên ~k~.

Kết quả

• In ra một số nguyên là số lượng lớn nhất các ký tự 'T' liên tiếp hoặc 'F' liên tiếp.

Giới hạn

• n == answerKey.length
• ~1 \le n \le 5 \cdot 10^4~
• answerKey[i] là 'T' hoặc 'F'
• ~1 \le k \le n~

Sample Input 1

TTFF
2

Sample Output 1

4

Giải thích

Ta đổi cả hai chữ 'F' thành 'T' để được "TTTT". Có 4 chữ 'T' liên tiếp.

Sample Input 2

TFFT
1

Sample Output 2

3

Giải thích

Đổi chữ 'T' đầu tiên thành 'F' để được "FFFT", hoặc đổi chữ 'T' thứ hai thành 'F' để được "TFFF". Trong cả hai trường hợp đều có 3 chữ 'F' liên tiếp.

Sample Input 3

TTFTTFTT
1

Sample Output 3

5

Giải thích

Đổi chữ 'F' thứ nhất để được "TTTTTFTT", hoặc đổi chữ 'F' thứ hai để được "TTFTTTTT". Trong cả hai trường hợp đều có 5 chữ 'T' liên tiếp.

Nguồn: LeetCode 2024.