ARC081E. Don't Be a Subsequence

$ ewcommand{dp}{mathsf{dp}}$ $ ewcommand{ ext}{mathsf{next}}$

Let $S$ be a string of lower case English letters. If there can be found all subsequences of length $L$ in $S$, then $S$ can be divided into $L$ segments, each contains all the 26 letters, which implies length of $S$ is at least $26L$.

This observation leads us to a solution. Let $dp[i]$ be the maximum number of the aforementioned segments that the suffix of $S$ that starts at index $i$ can be divided into. The DP can be done in $O(|S|)$ time. The shortest string that is not a subsequence of $S$ has a length of $M = dp[0] + 1$ ($S$ is 0-indexed).

Let $ ext[i][j]$ be the position of the first occurrence of letter $j$ to the right of position $i$ (including position $i$). We can compute the $ ext$ array in $O(26|S|)$ time.

Using the $ ext$ and $dp$ arrays, we can construct the answer as follows:
Start with an empty string $T$. Iterate the $dp[0] + 1$ positions of the answer string from left to right. For each position $i$, iterate over the letters from 'a' to 'z'. For each letter $j$, check whether it is possible to get an answer if we append $j$ to $T$. Let $k$ be position of the last letter of the first occurrence of $Tj$ in $S$ as a subsequence, it is ok to append letter $j$ to $T$ if the suffix $S[k + 1, |S|)$ does not contain all subsequences of length $M - |T| - 1$ i.e. $dp[k + 1] < M - |T| - 1$. This check can be done efficiently, see the following code for detail.

code

 
int main() {
  string s;
  scan(s);
  int n = SZ(s);
  vb vis(26);
  int cnt = 0;
  vi dp(n + 1);
  int length = 0;
  down (i, n - 1, 0) {
    if (!vis[s[i] - 'a']) {
      vis[s[i] - 'a'] = true;
      ++cnt;
      if (cnt == 26) {
        ++length;
        fill(all(vis), false);
        cnt = 0;
      }
    }
    dp[i] = length;
  }
vv next(n, vi(26));

fill(all(next.back()), n);

next.back()[s.back() - 'a'] = n - 1;

down (i, n - 2, 0) {

rng(j, 0, 26) {

next[i][j] = s[i] - 'a' == j ? i : next[i + 1][j];

}

}
++length;
int pos = 0;

while (length > 0) {

rng (j, 0, 26) {

int t = next[pos][j];

if (t < n && dp[t + 1] == length - 1) continue;

if (t < n) {

pos = t + 1;

}

cout << char('a' + j);

break;

}

--length;

}

cout << '
';

return 0;

}