Tutorial — Optimal String Deletion Strategy

Hãy xét tính chẵn lẻ của độ dài xâu $s$ để dự đoán khả năng xóa toàn bộ xâu ngay trong lượt đầu tiên của Hùng.

Khi độ dài $n$ là số lẻ lớn hơn $1$, Hùng có thể loại bỏ một xâu con có độ dài $n - 1$ để lại chính xác một ký tự ở hai đầu xâu.

Để tối đa hóa điểm số, Hùng nên chọn để lại ký tự nhỏ nhất giữa ký tự đầu tiên và ký tự cuối cùng của xâu $s$.