E - Don't Be a Subsequence

E - Don't Be a Subsequence

問題概略
文字列Sに対して、その中の部分列でない文字列のうち、一番短く辞書順最小のものを求めよ。

制約
10^5

解法
0文字目からスタートして、a~zについて、自分に一番近いところをとることを文字列の外に出るまで繰り返すことで存在しない文字列は作れる。
アルファベットを選ぶ時に一番短くなるようなもので、かつ、辞書順最小の物を選べば良い。
これを実現するには、それぞれのインデックスに自分以降で作れる最短の長さを持たせて、後ろから解けば良い。

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        String s = n();
        N = s.length();
        int[][] next = setNextChars(s);
        int[] len = new int[N + 2];
        int[] rec = new int[N + 1];
        fill(len, N);
        len[N + 1] = 0;
        for (int i = N ; i >= 0; i--) {
            len[i] = 1 << 30;
            for (int j = 25; j >= 0; j--) {
                //i文字目以降のjを使った時の最短
                int nlen = len[next[i][j] + 1] + 1;
                if (len[i] >= nlen) {
                    len[i] = nlen;
                    rec[i] = j;
                }
            }
        }
        String res = "";
        int cur = 0;
        while (cur < N + 1) {
            res += (char) ('a' + rec[cur]);
            cur = next[cur][rec[cur]] + 1;
        }
        System.out.println(res);
    }

    private static int[][] setNextChars(String s) {
        int n = s.length();
        int[][] next = new int[n + 1][26];
        fill(next, n);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                next[i][j] = next[i + 1][j];
            }
            next[i][s.charAt(i) - 'a'] = i;
        }
        return next;
    }