Độ 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

2038. Remove Colored Pieces if Both Neighbors are the Same Color – Xóa quân cờ nếu cả hai hàng xóm cùng màu (LeetCode, độ khó Medium)

Có ~n~ quân cờ xếp thành một hàng, mỗi quân được tô màu 'A' hoặc 'B'. Cho xâu colors độ dài ~n~, trong đó colors[i] là màu của quân thứ ~i~.

Alice và Bob chơi một trò chơi, hai người lần lượt thay phiên nhau xóa các quân cờ khỏi hàng. Trong trò chơi này, Alice đi trước.

• Alice chỉ được xóa một quân màu 'A' nếu cả hai quân kề bên nó cũng có màu 'A'. Alice không được xóa quân màu 'B'.
• Bob chỉ được xóa một quân màu 'B' nếu cả hai quân kề bên nó cũng có màu 'B'. Bob không được xóa quân màu 'A'.
• Alice và Bob không được xóa quân ở hai đầu hàng.
• Nếu đến lượt một người mà người đó không thể đi được nước nào thì người đó thua, người còn lại thắng.

Giả sử Alice và Bob đều chơi tối ưu, hãy trả về true nếu Alice thắng, hoặc false nếu Bob thắng.

Định dạng vào/ra để chạy thử trên máy: trên LeetCode các bạn chỉ cần viết hàm winnerOfGame trong class Solution. Để chạy được như một chương trình bình thường, mình đặt thêm định dạng:

Dữ liệu vào

• Một dòng chứa xâu colors.

Kết quả

• In true nếu Alice thắng, false nếu Bob thắng.

Giới hạn

• ~1 \le~ colors.length ~\le 10^5~
• colors chỉ gồm các chữ cái 'A' và 'B'.

Sample Input 1

AAABABB

Sample Output 1

true

Sample Input 2

AA

Sample Output 2

false

Sample Input 3

ABBBBBBBAAA

Sample Output 3

false

Nguồn: LeetCode 2038.