就考虑维护一个 $g_i$ 表示 $[g_i,i]$ 能被删除，且 $g_i$ 最大。

先初始化 $g_i$，枚举一个 $i$，如果 $s_{i-1}=s_i$，那么 $g_i=i-1$。

其余的 $g_i$ 就记 $x=g_{i-1}$，让 $x$ 去一直跳： $x\leftarrow g_{x-1}$，直到 $s_{x-1}=s_{i}$ 为止。

感觉每个位置至多被跳到一次啊，为什么要多乘一个字符集？

  for ( int i = 1; i <= n; i ++)
      if (s[i] == s[i - 1]) g[i] = i - 1;

  for ( int i = 1; i <= n; i ++) {
      if (g[i]) continue ;

      int x = g[i - 1];
      while (x) {
          if (s[x - 1] == s[i]) {
              g[i] = x - 1;
              break ;
          }

          x = g[x - 1];
      }
  }