CSES - Empty String

Author: Dong Liu

Table of Contents

EditorialImplementation

Editorial

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

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

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

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

Since we can remove the substring [i,k][i, k] and [k+1,j][k + 1, j] in any order, we also multiply this by ((ji+1)/2(ki+1)/2){(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

dp[i][j]=dp[i+1][k1]dp[k+1][j]((ji+1)/2(ki+1)/2)\texttt{dp}[i][j] = \sum{\texttt{dp}[i + 1][k - 1] * \texttt{dp}[k + 1][j] * {{(j - i + 1) / 2}\choose {(k - i + 1) / 2}}}

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

Implementation

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

C++

#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;
}

Python

N = 500
MOD = 10**9 + 7
def add(a: int, b: int) -> int:
return (a + b) % MOD
def mul(a: int, b: int) -> int:
return (a * b) % MOD

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!