実はほぼ貪欲でOKだった。
ただサンプルが弱くて実装に罠があるから難しい。
先頭は任意の文字数消すことができる（①）。
先頭以外で、backspaceを押すことは、2文字スキップすることと等しい（②）。
②より、最後に余る文字は偶数個（0を含む）である必要がある（③）。
まずはこれだけに気づける。
②は実際の操作の言い換えでしかない。
さらに、1文字進めることは次のインデックスをインデックス+1、連続でstep回2文字スキップすることはインデックス+となるので、次のインデックスとして選べるインデックスの偶奇は一意に定まる。
（偶数からは奇数、奇数からは偶数にしか移動できない）
また「..A..A..B」または「..A..AB」のような状態のときに、「AB」と選ぶとして、最初の「A」をスキップする意味はない。仮に2番目の「A」を選んだとき、選べる「B」には、最初の「A」を選んでも同様に到達できる（何回連続スキップしても移動できるインデックスの偶奇が変わらないので）。
よって文字の選び方は前から貪欲でOK（④）。
以上から、
偶数インデックス、奇数インデックスそれぞれから開始する（⑤）と、偶奇偶奇...または奇偶奇偶...とインデックスを選ぶことができる。
まとめ
- ①、⑤より、
をsの偶数、奇数インデックスそれぞれから開始する。
- ④より
まで貪欲に選ぶ。
- ③を満たすように終了する。
以上を満たすように丁寧に実装することでAC。
いくつか罠があって、
③を満たすように終了しないといけないので、このときインデックスの取り扱いに注意。
偶数インデックスから始める、奇数インデックスから始めるの両方を試す必要がある。
