Cho chuỗi s chứa chữ cái in hoa và thường. Chuỗi được gọi là "tốt" nếu không có hai ký tự liền kề nào là cùng một chữ cái nhưng khác chữ hoa/thường (ví dụ: 'aA' hoặc 'Aa').
Để biến chuỗi thành tốt, ta xóa các cặp ký tự liền kề vi phạm quy tắc cho đến khi chuỗi tốt (chuỗi rỗng cũng được coi là tốt).
Ví dụ: s = "popPpulaBbr" → "popular" (xóa 'pP' hoặc 'Pp' và 'Bb').
Thuật toán
- Khởi tạo danh sách res rỗng.
- Duyệt từng ký tự ch trong s:
- Nếu res không rỗng và phần tử cuối cùng cùng chữ cái nhưng khác chữ hoa/thường với ch, xóa phần tử cuối.
- Ngược lại, thêm ch vào cuối res.
- Nối các phần tử trong res và trả về.
Ví dụ (Python)
def solve(s):
res = []
for ch in s:
if res and res[-1] != ch and res[-1].lower() == ch.lower():
res.pop()
else:
res.append(ch)
return ''.join(res)
s = "popPpulaBbr"
print(solve(s))
Đầu vào
"popPpulaBbr"
Đầu ra
popular