これと同じでは！？

問題概要

長さ $N$ の文字列 $S$ が与えられる。

いま、文字列の各 index に色を塗ることを考える。色を塗ったあと、隣接する異なる色をもつ 2 文字を swap することができる。swap した結果得られる文字列がソートされている状態となるようにしたい。

このようなことが可能な色の塗り方のうち、色の種類数の最小値を求めよ。また具体的な色の塗り方を復元せよ。

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

これの Easy Version は「2 色で可能か？」という問題。
Hard Version が解ければ、最小値が 2 以下かどうかを判定すればよいだけなので、Hard を解くことにした。

さて、最初に思ったのは、

同じ色同士の順序は入れ替えられない
(同じ色同士の順序がきちんと単調増加になっていることを前提の下で) 異なる色同士の順序は好きなように入れ替えることができる

ということ。これは要するに、冒頭に貼った ABC の過去問と一緒なのだ。こんな感じの Greedy で解くことができる。たとえば abcbabdcb という文字列の場合

index	行動	結果
1 文字目	この a はまずは 1 色目で塗る	1 色目が (a)
2 文字目	この b も 1 色目で塗れる	1 色目が (a, b)
3 文字目	この c も 1 色目で塗れる	1 色目が (a, b, c)
4 文字目	この b は、1 色目の最後尾が c なので 2 色目が必要になる	1 色目が (a, b, c)、2 色目が (b)
5 文字目	この a は、1, 2 色目のいずれも無理で、3 色目が必要になる	1 色目が (a, b, c)、2 色目が (b)、3 色目が (a)
6 文字目	この b は、1 色目として塗るのは無理だが、2 色目で塗ることができる	1 色目が (a, b, c)、2 色目が (b, b)、3 色目が (a)
7 文字目	この d は、1 色目として塗れる	1 色目が (a, b, c, d)、2 色目が (b, b)、3 色目が (a)
8 文字目	この c は、2 色目として塗れる	1 色目が (a, b, c, d)、2 色目が (b, b, c)、3 色目が (a)
9 文字目	この b は、3 色目として塗れる	1 色目が (a, b, c, d)、2 色目が (b, b, c)、3 色目が (a, b)

というわけで、"abcbabdcb" の場合、3 色で塗ることができる。毎回「何色目として塗れば良いか」を求める部分は、実は二分探索で高速に求めることができる。たとえば上の表の 8 文字目を処理する部分に着目しよう。処理する前の時点で、各色の最後尾は

1 色目： d
2 色目： b
3 色目： a

となっている。8 文字目の c を挿入すべき場所は、「初めて c 以下の文字が登場する箇所」である。これは二分探索で求められる。実装上は、この d, b, a といった並びが単調増加であって欲しいので、符号反転して扱うことにした。

余談

実はこの問題の答えは、LIS の反対の LDS (最長単調減少部分列) と一致する。

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

int N;
string S;

void solve() {
    N = S.size();
    vector<int> col(N, 0);
    vector<int> vec;
    for (int i = 0; i < N; ++i) {
        int id = 50 - (S[i] - 'a');
        if (vec.empty()) {
            col[i] = 0;
            vec.push_back(id);
        }
        else {
            int it = lower_bound(vec.begin(), vec.end(), id) - vec.begin();
            if (it >= vec.size()) {
                col[i] = vec.size();
                vec.push_back(id);
            }
            else {
                col[i] = it;
                vec[it] = id;
            }
        }
    }
    cout << vec.size() << endl;
    for (int i = 0; i < N; ++i) {
        if (i) cout << " ";
        cout << col[i]+ 1;
    }
    cout << endl;
}

int main() {
    while (cin >> N >> S) solve();
}