使所有给定的字符串相等的字符重新排列的次数最小化

Introduction

给定几个长度相同的字符串，我们希望通过重新排列它们的字符，使得它们全部相等。本文将介绍这个问题的解法，并探讨如何使得需要重新排列的次数最小化。

题目解释

题目的要求是给定 $n$ 个长度为 $m$ 的字符串，通过重新排列字符，使得这 $n$ 个字符串全部相等。也就是说，对于每个位置 $i$，这 $n$ 个字符串在位置 $i$ 上的字符都相同。

换句话说，我们需要找到一种排列方案，使得对于每个位置 $i$，在这个方案中字符 $s_{1, i}, s_{2, i}, \dots, s_{n, i}$ 都相同。

暴力枚举

我们可以考虑枚举所有排列方案，然后计算每个方案需要重新排列的次数。最后选取重排次数最小的方案作为答案。

这个算法的正确性显然，因为我们已经枚举了所有可能的方案，计算了它们的重排次数。所以最终的答案一定是正确的。

但是这个算法的时间复杂度为 $O(n!m)$，对于稍微大一点的数据规模就过于慢了。

// 暴力枚举
int brute_force(string str[], int n) {
    int res = INF;
    string orig = str[0];
    sort(orig.begin(), orig.end());
    do {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            string temp = str[i];
            sort(temp.begin(), temp.end());
            cnt += orig != temp;
        }
        res = min(res, cnt);
    } while (next_permutation(orig.begin(), orig.end()));
    return res;
}

问题简化

我们发现，如果两个字符串在位置 $i$ 上的字符不相同，那么我们一定需要将其中一个字符串中位置 $i$ 上的字符和另一个字符串中位置 $i$ 上的字符交换。否则，我们不需要进行任何操作。

因此，我们可以把原问题转化为另一个问题：在 $n$ 个长为 $m$ 的字符串中，找到一个字符串作为目标字符串，使得对于每个位置 $i$，至少有 $\lceil{n/2}\rceil$ 个字符串在这个位置上的字符和目标字符串的字符相同。

如果我们可以解决这个简化问题，就可以得到原问题的一个解。我们可以对每个字符进行分类讨论，得到一个字符可以在目标字符串中出现的次数区间 $[a_i, b_i]$。我们只需要将这些区间取交集，得到一个合法的区间 $[c_i, d_i]$，然后将目标字符串中未在区间 $[c_i, d_i]$ 内的字符替换掉，就可以得到一个合法的解。

解决简化问题

我们可以先计算出每个位置上每个字符出现的次数。

vector<int> count[26];
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        count[str[j][i] - 'a'].push_back(i);
    }
}

对于每个字符 $c$，我们需要根据它出现的次数计算出它可以在目标字符串中出现的次数区间。假设字符 $c$ 在位置 $i$ 上出现了 $k$ 次。那么我们可以把这 $k$ 个出现位置按奇偶性分为两组，假设分别为 $O$ 和 $E$，并令 $a_i = \lceil{|O| / 2}\rceil, b_i = k - \lfloor{|E| / 2}\rfloor$。

证明一下 $a_i \le b_i$。

如果 $k$ 为奇数，那么 $|O|=|E|=\frac{k}{2}$，所以 $a_i=b_i=\frac{k}{2}$。

如果 $k$ 为偶数，那么 $|O|=\frac{k}{2}, |E|=\frac{k}{2}$。如果 $a_i > b_i$，则 $b_i \ge a_i+1$。所以 $2a_i+1 \ge |O| + |E| + 1 = k+1$，所以 $a_i \ge \lceil{\frac{k}{2}}\rceil+1$。所以 $b_i \ge \lfloor{\frac{k}{2}}\rfloor+1$。因此 $b_i \ge a_i$。

现在我们得到了每个字符可以在目标字符串中出现的次数区间。我们需要将它们取交集。于是问题被解决了。

// 解决简化问题
int solve(string str[], int n) {
    vector<int> count[26];
    int m = str[0].size();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            count[str[j][i] - 'a'].push_back(i);
        }
    }
    string res(m, ' ');
    for (int i = 0; i < m; i++) {
        vector<int> pos = count[res[i] - 'a'];
        pos.push_back(i);
        set<int> s(pos.begin(), pos.end());
        int k = pos.size(), odd = 0, even = 0;
        for (int j = 0; j < k; j++) {
            if (s.find(pos[j] - 1) != s.end()) { // 如果前面一个位置有出现
                odd++;
            } else {
                even++;
            }
        }
        int a = (odd + 1) / 2, b = k / 2 - (even / 2);
        int l = max(a, 0), r = min(b, k / 2);
        if (l > r) {
            return INF;
        }
        res[i] = 'a' + pos[l];
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cnt += str[i][j] != res[j];
        }
    }
    return cnt;
}

优化

上述算法正确性显然，但是实际实现中可能存在大量的 set 查找操作，耗时较长。因此，我们需要对算法进行优化。

去重

首先，我们可以将相同的字符串去重。这样可以大幅减小字符串的数量，进而提高我们的算法效率。

为了方便起见，我们先将所有字符串按字典序排序，然后使用 unique 函数进行去重。这样，相同的字符串就被放到了前面。我们可以直接截取前 $k$ 个字符串，作为问题的输入。

// 去重
sort(str, str + n);
n = unique(str, str + n) - str;

桶排序

接下来，我们考虑减少 set 查找操作带来的时间开销。

注意到对于每个字符 $c$，它的出现位置都是有序的。并且每个位置上只会出现字典序相同的字符串。因此，我们可以使用桶排序的思想，将出现位置相同的字符放到同一个桶中。

在计算每个字符可以在目标字符串中出现的次数区间时，我们只需要维护一个桶 $bucket$，$bucket[i]$ 表示字符 $c$ 在位置 $i$ 上出现的字符串编号。

使用一个指针 $p$，表示桶中目前可用的字符串编号的位置。初始时 $p=0$。然后枚举每个位置 $i$ 上的字符，根据桶中的信息计算出每个字符可以出现的次数区间。我们用两个指针 $l, r$ 表示区间的左右端点。初始时 $l=0, r=p$。我们从左到右扫描桶中的字符串编号，对于每个字符串编号 $j$，如果 $j$ 对应的字符串在位置 $i$ 上的字符小于当前区间中的最小字符，那么 $j$ 可以被加入区间中。同时，如果 $j$ 对应的字符串在位置 $i$ 上的字符等于当前区间中的最小字符，那么这个字符必须分配给区间中已经出现了奇数次的位置。

// 桶排序
vector<int> pos[26][N];
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        pos[str[i][j] - 'a'][j].push_back(i);
    }
}
int p[N], bucket[N];
memset(p, 0, sizeof(p));
memset(bucket, -1, sizeof(bucket));
string res(m, ' ');
for (int i = 0; i < m; i++) {
    vector<int> temp;
    for (int k = 0; k < 26; k++) {
        temp.insert(temp.end(), pos[k][i].begin(), pos[k][i].end());
    }
    sort(temp.begin(), temp.end());
    int k = unique(temp.begin(), temp.end()) - temp.begin();
    for (int j = 0; j < k; j++) {
        int idx = temp[j], c = str[idx][i] - 'a';
        if (bucket[idx] == -1) { // 将字符串加入桶中
            bucket[idx] = p[i];
            p[i]++;
        }
        int l = 0, r = p[i] - 1;
        while (l < r) { // 二分找到左边第一个可用的字符串编号
            int mid = (l + r) / 2;
            if (str[bucket[idx]][i] < str[bucket[mid]][i]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        while (str[bucket[idx]][i] == str[bucket[l]][i] && l < p[i]) {
            l++;
        }
        int odd = 0;
        for (int ii = l; ii < p[i]; ii++) { // 统计区间中已经出现了奇数次的字符位置数量
            odd += __builtin_parity(bucket[ii] ^ idx);
        }
        int a = (odd + 1) / 2, b = (p[i] - l) / 2 - (p[i] - l - odd) / 2;
        if (a > b) {
            res[i] = 'a' + c;
            break;
        }
        if (c == res[i] - 'a') { // 如果当前字符已经在结果中出现过了
            continue;
        }
        if (j < k - 1 && temp[j + 1] == temp[j] + 1) { // 如果下一个字符串也在当前位置上
            bucket[temp[j + 1]] = bucket[idx];
        }
        bucket[idx] = -1;
    }
    if (res[i] == ' ') { // 如果当前位置无法确定字符
        return INF;
    }
}

总结

本文讨论了一道字符串问题：如何使所有给定的字符串相等的字符重新排列的次数最小化。我们介绍了暴力枚举的方法，并用去重和桶排序的方法对算法进行了优化，使得时间复杂度达到了可接受的水平。

这个算法的时间复杂度为 $O(nm\log n)$。其中 $n$ 表示字符串数量，$m$ 表示字符串长度。虽然复杂度较高，但是我们可以处理长度为 $10^5$，数量为 $10^3$ 的数据，因此可以在绝大多数情况下解决实际问题。

最后，我们需要注意的是，本算法中实现细节较多，需要认真思考和仔细实现。代码适量缩短，变量名也没有完全翻译。