「同じ文字が連続してる場合、後ろにある文字を消すことが出来ない」という条件で \(T\) から \(1\) 文字ずつ消していく手順を数えればよいです。

\(T\) の先頭に文字 ^ を追加した上で、「連続する \(2\) 文字 \(x,y\) であって \(x \ne y\) であるものを選び、\(x\) に置き換える」という操作を \(1\) 文字になるまで行う手順を数える問題に言い換えます。（もっと一般に 「\(f(x,y)\) に置き換える」と思ってもよいです。）

これは区間 dp により \(O(N^3 k^2)\) （\(k\) は文字種とする）で解くことが出来ます。（\(f(x,y)=x\) であることを利用すると \(O(N^3)\) に出来ます。）

（イメージとしては、操作を表す二分木とそのトポロジカル順の個数を数える、と考えるとよいです。）

• \(O(N^3 k^2)\) 解
• \(O(N^3)\) 解