Tutorial — Chuỗi Đảo

Vì thao tác tráo đổi các ký tự là miễn phí, thứ tự ban đầu của các ký tự trong $s$ không giới hạn việc chọn tập hợp ký tự để tạo ra chuỗi $t$. Chi phí duy nhất đến từ số lượng ký tự bị xóa, do đó mục tiêu là tạo ra chuỗi hợp lệ $t$ có độ dài lớn nhất.

Để chuỗi $t$ có độ dài $m$ hợp lệ, mỗi vị trí $i$ từ $1$ đến $m$ của $t$ phải có ký tự khác với $s_i$. Điều này có nghĩa là mỗi vị trí $s_i = 0$ đòi hỏi một ký tự $1$ từ $s$, và mỗi vị trí $s_i = 1$ đòi hỏi một ký tự $0$ từ $s$.

Chúng ta đếm tổng số ký tự $0$ và $1$ trong $s$, sau đó duyệt $s$ từ đầu đến cuối để tham ăn ghép ký tự đối lập cho từng vị trí $i$. Độ dài $m$ lớn nhất đạt được khi chúng ta gặp vị trí đầu tiên thiếu ký tự đối lập, và đáp án là $|s| - m$.