CSES - Empty String

Time Complexity: $\mathcal{O}(N^3)$

Let $\texttt{dp}[i][j]$ represent the number of ways to empty the substring $[i, j]$.

To calculate $\texttt{dp}[i][j]$, we loop through indices $k$ between $i$ and $j$ where $s[i] = s[k]$.

Then, if we choose to remove $s[i]$ and $s[k]$, we must remove the range $[i + 1, k - 1]$ first (for $s[i]$ and $s[k]$ to be adjacent). Here, the number of ways to remove the range $[i + 1, k - 1]$ is $\texttt{dp}[i + 1][k - 1]$.

We also need to remove $[k + 1, j]$ for the whole substring $[i, j]$ to be removed (the number of ways to do this is $dp[k + 1][j]$).

Since we can remove the substring $[i, k]$ and $[k + 1, j]$ in any order, we also multiply this by ${(j - i + 1) / 2}\choose {(k - i + 1) / 2}$ (notice that we divide the sizes by two because we remove the letters in pairs).

Thus our transition would be

such that $s[i] = s[k]$.

Copy
#include <bits/stdc++.h>
using namespace std;

#define N 500
#define MOD 1000000007

int add(int a, int b) {
	if ((a += b) >= MOD) a -= MOD;
	return a;
}