Remove Colored Pieces if Both Neighbors are the Same Color (LeetCode 2038)

Nguồn: LeetCode 2038 Độ khó: Trung bình Tham lam Xâu Đếm

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

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.

Ràng buộc:

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

Đị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 (và dùng được khung chạy tay bên dưới), 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.

2038. Remove Colored Pieces if Both Neighbors are the Same Color (LeetCode, Medium)

There are n pieces arranged in a line, and each piece is colored either by 'A' or by 'B'. You are given a string colors of length n where colors[i] is the color of the ith piece.

Alice and Bob are playing a game where they take alternating turns removing pieces from the line. In this game, Alice moves first.

• Alice is only allowed to remove a piece colored 'A' if both its neighbors are also colored 'A'. She is not allowed to remove pieces that are colored 'B'.
• Bob is only allowed to remove a piece colored 'B' if both its neighbors are also colored 'B'. He is not allowed to remove pieces that are colored 'A'.
• Alice and Bob cannot remove pieces from the edge of the line.
• If a player cannot make a move on their turn, that player loses and the other player wins.

Assuming Alice and Bob play optimally, return true if Alice wins, or return false if Bob wins.

Example 1: Input: colors = "AAABABB" – Output: true
Explanation:
AAABABB -> AABABB
Alice moves first.
She removes the second 'A' from the left since that is the only 'A' whose neighbors are both 'A'.
Now it's Bob's turn.
Bob cannot make a move on his turn since there are no 'B's whose neighbors are both 'B'.
Thus, Alice wins, so return true.

Example 2: Input: colors = "AA" – Output: false
Explanation:
Alice has her turn first.
There are only two 'A's and both are on the edge of the line, so she cannot move on her turn.
Thus, Bob wins, so return false.

Constraints:

• 1 <= colors.length <= 105
• colors consists of only the letters 'A' and 'B'

Ví dụ 1 – LeetCode

Input: colors = "AAABABB"
Output: true

Ví dụ 1 – stdin / stdout

AAABABB
---
true

Ví dụ 2 – LeetCode

Input: colors = "AA"
Output: false

Ví dụ 2 – stdin / stdout

AA
---
false

Giải thích ví dụ của đề:

• Ví dụ 1: Alice đi trước, xóa quân 'A' thứ hai tính từ trái (AAABABB → AABABB) vì đó là quân 'A' duy nhất có cả hai hàng xóm đều là 'A'. Tới lượt Bob, không có quân 'B' nào có hai hàng xóm đều là 'B' nên Bob không đi được. Vậy Alice thắng, trả về true.
• Ví dụ 2: Alice đi trước, nhưng chỉ có hai quân 'A' và cả hai đều ở đầu hàng nên Alice không đi được. Vậy Bob thắng, trả về false.

Lời mở đầu

Bài này 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 😇.

Lưu ý nhỏ: khi nộp trên CLUE OJ các bạn dán toàn bộ code, gồm cả hàm main, vì đề trên CLUE OJ đọc dữ liệu vào và in kết quả đúng theo định dạng ở phần đề bài, giống như khi các bạn chạy thử trên máy hoặc ở trang Chạy code online của blog.

Tóm tắt đề bài: 2 người A (Alice) và B (Bob) chơi một trò chơi như sau: có một xâu $s$ gồm các ký tự 'A' và 'B'. Đến lượt mình, người A chọn một ký tự 'A' sao cho ký tự liền trước và liền sau nó cũng là 'A' rồi xóa ký tự này khỏi xâu. Người B cũng tương tự nhưng chọn ký tự 'B'. Người nào không còn chọn được ký tự nữa thì thua. Hỏi ai thắng nếu A đi trước.

Thêm một ví dụ cho dễ hình dung: "ABBBBBBBAAA". Alice chỉ có đúng 1 nước (xóa chữ A ở giữa khúc AAA cuối), còn Bob có khúc 7 chữ B nên xóa được tới 5 lần. Alice đi 1 nước, Bob đi 1 nước, tới lượt Alice thì hết nước đi ⇒ Bob thắng, đáp án false.

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 1Đếm AAA, BBB + mô phỏng · O(|s|)

Cách 1Đếm số nước đi của mỗi người – O(|s|)

Phương pháp giải: Tham lam. Thoạt nhìn đây là bài trò chơi đối kháng, nghe "chơi tối ưu" là dễ nghĩ tới vét cạn trạng thái. Nhưng để ý kỹ thì nước đi của hai người hoàn toàn không ảnh hưởng tới nhau:

• Alice chỉ xóa được chữ A nằm giữa ba chữ AAA liên tiếp. Xóa xong, hai chữ A hai bên vẫn là A và nhập lại với nhau, nên các khúc chữ B không hề thay đổi ⇒ số nước đi của Bob giữ nguyên.
• Một khúc gồm $L \ge 3$ chữ A liên tiếp cho Alice đúng $L - 2$ nước đi, dù xóa theo thứ tự nào: mỗi lần xóa khúc ngắn đi 1, tới khi còn 2 chữ thì hết xóa được. Và $L - 2$ cũng chính là số bộ ba AAA liên tiếp nằm trong khúc đó.

Ý tưởng chính

Gọi $cntA$ là số lượng ký tự A mà người A có thể xóa: ta chỉ việc đếm số xâu con AAA xuất hiện liên tiếp trong xâu (đếm theo cửa sổ 3 ký tự, các cửa sổ được phép chồng lên nhau). Tương tự với $cntB$ là số ký tự B mà người B có thể xóa (đếm số BBB).

Khi đã có $cntA$ nước đi của A và $cntB$ nước đi của B, ta chỉ việc thực hiện như luật chơi: tới lượt A thì giảm $cntA$ xuống 1 đơn vị rồi chuyển sang lượt B, và ngược lại. Tới lượt ai mà số nước đi của người đó đã về 0 thì người đó thua: nếu $cntA$ cạn trước thì B thắng, nếu $cntB$ cạn trước thì A thắng.

Gọn hơn nữa

Mô phỏng như trên tương đương với điều kiện: Alice thắng khi và chỉ khi $cntA \gt cntB$. (Nếu $cntA \le cntB$ thì sau $cntA$ lượt mỗi người, tới lượt Alice đã hết nước đi.) Vòng while chạy tối đa khoảng $2 \cdot \min(cntA, cntB) + 2$ lần nên vẫn là $O(|s|)$, các bạn viết kiểu nào cũng được.

Minh hoạ: đếm rồi chơi thật

Em nhập xâu (tối đa 30 ký tự) rồi bấm Tiếp. Phần đầu là trượt cửa sổ 3 ký tự (viền vàng) để đếm AAA, BBB. Phần sau cho hai người chơi thật trên xâu: mỗi lượt xóa một quân hợp lệ (viền xanh), các bạn sẽ thấy mỗi nước đi chỉ làm số nước của chính người đó giảm 1:

colors

Ví dụ nhanh:

Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé. Biến flag = true nghĩa là đang tới lượt A (Alice), false là tới lượt B (Bob):

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

class Solution {
public:
    bool winnerOfGame(string s) {
        int cntA = 0;
        int cntB = 0;
        for (int i = 0; i < (int) s.size() - 2; i++) {
            if (s[i] == 'A' && s[i + 1] == 'A' && s[i + 2] == 'A') {
                cntA++;
            }
            if (s[i] == 'B' && s[i + 1] == 'B' && s[i + 2] == 'B') {
                cntB++;
            }
        }
        bool flag = true;
        while (true) {
            if (flag == true) {
                if (cntA > 0) {
                    cntA--;
                    flag = false;
                }
                else {
                    return false;
                }
            }
            else {
                if (cntB > 0) {
                    cntB--;
                    flag = true;
                }
                else {
                    return true;
                }
            }
        }
    }
};

int main() {
    string colors;
    cin >> colors;
    Solution sol;
    cout << (sol.winnerOfGame(colors) ? "true" : "false");
    return 0;
}

import sys

class Solution:
    def winnerOfGame(self, s: str) -> bool:
        cntA = 0
        cntB = 0
        for i in range(len(s) - 2):
            if s[i] == 'A' and s[i + 1] == 'A' and s[i + 2] == 'A':
                cntA += 1
            if s[i] == 'B' and s[i + 1] == 'B' and s[i + 2] == 'B':
                cntB += 1
        flag = True
        while True:
            if flag:
                if cntA > 0:
                    cntA -= 1
                    flag = False
                else:
                    return False
            else:
                if cntB > 0:
                    cntB -= 1
                    flag = True
                else:
                    return True

def main():
    colors = sys.stdin.read().split()[0]
    print("true" if Solution().winnerOfGame(colors) else "false")

if __name__ == "__main__":
    main()

Cẩn thận với s.size() - 2

s.size() có kiểu không dấu (size_t). Nếu viết i < s.size() - 2 mà xâu chỉ dài 1 hoặc 2 thì s.size() - 2 bị tràn thành một số cực lớn, vòng lặp chạy ra ngoài xâu. Vì vậy trong code mình ép kiểu (int) s.size() - 2 trước khi trừ, lúc đó kết quả là $-1$ hoặc $0$ và vòng lặp không chạy lần nào.

Khung chạy tay bên dưới chạy đúng từng dòng của code C++ ở trên (cả hàm main lẫn hàm trong class Solution):

C++▶ Chạy tay từng dòng codeĐếm số bộ AAA và BBB liên tiếp rồi mô phỏng lần lượt từng lượt chơi, O(|s|).

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

Dữ liệu mẫu:

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

2using namespace std;

3

4class Solution {

5public:

6 bool winnerOfGame(string s) {

7 int cntA = 0;

8 int cntB = 0;

9 for (int i = 0; i < (int) s.size() - 2; i++) {

10 if (s[i] == 'A' && s[i + 1] == 'A' && s[i + 2] == 'A') {

11 cntA++;

12 }

13 if (s[i] == 'B' && s[i + 1] == 'B' && s[i + 2] == 'B') {

14 cntB++;

15 }

16 }

17 bool flag = true;

18 while (true) {

19 if (flag == true) {

20 if (cntA > 0) {

21 cntA--;

22 flag = false;

23 }

24 else {

25 return false;

26 }

27 }

28 else {

29 if (cntB > 0) {

30 cntB--;

31 flag = true;

32 }

33 else {

34 return true;

35 }

36 }

37 }

38 }

39};

40

41int main() {

42 string colors;

43 cin >> colors;

44 Solution sol;

45 cout << (sol.winnerOfGame(colors) ? "true" : "false");

46 return 0;

47}

ChậmVừaNhanhRất nhanh

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

• Không gian: chỉ dùng vài biến đếm nên là $O(1)$ (không tính xâu đầu vào).
• Thời gian: vòng for duyệt xâu một lần $O(|s|)$, vòng while chạy không quá $cntA + cntB + 1 \le 2|s|$ lần, tổng cộng $O(|s|)$ với $|s|$ là độ dài xâu.

Không gian$O(1)$

Thời gian$O(|s|)$

Ghi chú của mình: code C++ và Python đều cho đúng 2 ví dụ của đề, và đã được so với một chương trình vét cạn trò chơi thật (thử mọi nước xóa của cả hai người, có nhớ trạng thái) trên 500 xâu ngẫu nhiên độ dài tới 13 – khớp hết. Với xâu dài $10^5$, bản C++ chạy khoảng 0.01 giây, bản Python khoảng 0.06 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 😇