This can be solved with dp in O(n³)

Say dp[i][j] is the number of possible ways to remove exactly substring [i, j]. Obviously, dp[i][i + 1] = (s[i] =  = s[i + 1]).

Now to calculate dp[i][j] let's check with which position was s[i] deleted. If we deleted s[i] with s[k], it has to be s[k] = s[i] and then we had to delete [i + 1, k - 1] separately (and, therefore, to delete [k + 1, j] separately. So we get dp[i + 1][k - 1] ways to delete [i, k] in this manner and dp[k + 1][j] to delete [k + 1, j]. Note that deletions in those substrings are independent and don't afffect each other. So to get total number of possible ways, we have to multiply this by . In total, we get the following dp:

Hope that helps

Please tell me, how to create an account on that site?