---
# System prepended metadata

title: 2038. Remove Colored Pieces if Both Neighbors are the Same Color

---

# 1. Tóm tắt đề bài
Cho xâu **$s$** chỉ gồm các kí tự là **'A'** và **'B'**. Alice đi **trước** và Bob đi sau. Trong lượt của ai thì người đó phải xóa đi $1$ chữ cái trong xâu **$s$** sao cho chữ cái đấy giống hệt hai chữ cái bên cạnh nó. Tuy nhiên Alice thì chỉ được xóa chữ **'A'** và Bob chỉ được xóa chữ **'B'** và họ không thể xóa chữ cái đầu tiên và cuối cùng của xâu.
Nếu đến lượt ai mà không thực hiện được lượt chơi của mình thì người đó thua.
Trả về **true** nếu Alice thắng và **false** nếu Bob thắng.

### Giới hạn

$1 \le s.length() \le 10^5$


# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(n)$**

Đếm số bộ ba kí tự liên tiếp giống nhau của **'A'** và **'B'** và so sánh số lượng của $2$ cái.


# 3. Lời giải chi tiết

Định nghĩa: $cntA$, $cntB$ là số lượng kí tự có thể xóa được của **'A'** và **'B'**.

Ta thấy, với mọi xâu chỉ gồm các kí tự giống nhau mà có  $length() \le 2$ thì sẽ không thể xóa được nữa theo yêu cầu của đề bài và sẽ luôn không đổi. Và với mọi xâu chỉ gồm $1$ kí tự và có $3 \le length()$ thì nếu xóa hết những kí tự xóa được thì sẽ luôn trở thành một xâu có $length() = 2$ và không thể xóa được nữa và sẽ luôn tồn tại trong xâu chính.

Ví dụ: Cho xâu $s$ = "ABBBBAA".
* Bước 1: Ta xóa phần tử $s[2]$ và xâu $s$ trở thành s = "ABBBAA"
* Bước 2: Xóa $s[2]$ tương tự bước 1, xâu mới thu được là s = "ABBAA" và không thể xóa thêm được nữa.

Như vậy, ta sẽ không thể xóa hoàn toàn một xâu con chỉ gồm toàn chữ $B$ để nối 2 xâu chỉ gồm chữ $A$ lại với nhau.

Kết luận: 

Duyệt qua xâu từ vị trí $1$ đến $s.length()-1$ và kiểm tra xem vị trí đó có giống phần tử đứng trước và sau nó không nếu có thì cộng $1$ vào $cntA$ hoặc $cntB$ tương ứng.

Vì Alice đi **trước** nên là Alice chỉ thắng khi có nhiều lượt chơi hơn hẳn so với Bob.

### Độ phức tạp thuật toán

Thời gian: $O(n)$ Vì chỉ cần duyệt qua xâu $s$ một lần. 

Bộ nhớ mở rộng: $O(1)$

### Code mẫu

[here](https://leetcode.com/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color/submissions/1064637634/)
