思路与算法

每词的最小重排为升序，最大重排为降序。要某词严格最小，只需比较其升序串与其他词降序串的最小者；维护降序最小和次小并排除自身。

正确性说明

任意词可通过交换实现任意字符排列，所以自身选最小排列、其余各选最大排列是对当前词最有利的独立操作。该构造能严格小于每个其他最大串当且仅当存在可行方案，因此与除自身外最小最大串比较为充要条件。

复杂度

O(n(m+26))期望字节扫描时间（字符串比较最坏每次O(m)），O(nm)存升序串，含计数排序、两最小值更新和比较。

易错点

严格小于，不是小于等于；不同原词可能互为字母排列，最大串可相同，两个最小值必须保留重复值。n=1输出1。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> lo(n);
    string first(m + 1, 'z'), second = first;
    int who = -1;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int cnt[26] = {};
        for (char c : s)
            cnt[c - 'a']++;
        string hi;
        for (int c = 0; c < 26; c++)
            lo[i] += string(cnt[c], char('a' + c));
        for (int c = 25; c >= 0; c--)
            hi += string(cnt[c], char('a' + c));
        if (hi < first) {
            second = first;
            first = hi;
            who = i;
        } else if (hi < second)
            second = hi;
    }
    for (int i = 0; i < n; i++)
        cout << (n == 1 || lo[i] < (i == who ? second : first) ? '1' : '0');
    cout << "\n";
}