Tutorial — Chiến Thuật Lật Xâu

Nhận xét rằng các phép đảo ngược xâu của Lan chỉ làm thay đổi định hướng tương đối giữa hai xâu $A$ và $B$ qua lại giữa hướng ban đầu và hướng bị đảo ngược.

Đếm số vị trí khác nhau $c_1$ giữa $A$ và $B$, cùng số vị trí khác nhau $c_2$ giữa $A$ và $\operatorname{rev}(B)$. Tổng số lượt đi cho mỗi mục tiêu hướng sẽ phụ thuộc trực tiếp vào tính chẵn lẻ của $c_1$ hoặc $c_2$ do sự xen kẽ lượt đảo xâu của Lan.

Tính số lượt đi tối thiểu $ans_1$ cho hướng ban đầu và $ans_2$ cho hướng đảo ngược bằng các công thức theo tính chẵn lẻ của $c_1$ và $c_2$, sau đó kết quả tối ưu là $\min(ans_1, ans_2)$.