使用最少的操作将给定的字符串转换为已排序的字符串

Question

我们给了一个任意的字符串.现在,我们可以对此字符串执行一些操作.任何字母都可以转换为任何其他字母.现在,我们可以从字符串中选择任何字母并将其转换为任何其他字母.这将被称为单个操作.

我们如何使用如上所述的最小操作数将字符串转换为字母按排序顺序排列的字符串？

所有解决方案,包括开箱即用的解决方案都是受欢迎的!

PS:这是一个例子 -

Given string: dcba
We can convert this string into a sorted using at least 3 operations. The generated string can be any of the following:
dddd (3 operations)
aaaa (3 operations)
cccc (3 operations)
..
etc.

PPS:正如有些人所说,我在这里提供自己的解决方案 -

其中一个暴力解决方案是利用递归.当我们处于字符串的某个字符索引时,我们可以不更改它或将其更改为其他字符,并递归调用索引递增1的函数.如果我们改变角色,增加号码.1的操作只是按原样传递.在递归的每一步,我们都可以检查字符串是否排序 - 如果是,则用当前计数更新总体最小值,如果它小于当前计数.

Answer 1

这个问题等同于你的字符串中增长最长的子序列:显然,保持最大字母数不变是最佳的,并且这些字母必须形成一个增加的子序列.另一个方向类似.

虽然LIS可以在一般序列的O(n log n)中求解,但您甚至不需要它,因为您手头有一个更简单的特殊情况,字母大小为a = 26.您可以使用动态编程来解决问题在O(n·a):

设f(i,j)是以字母j结尾的前缀s [0 ..(i-1)]的最优解.我们已经复发了

f(0, j) = 0  for j = 0..25
f(i + 1, j) = [j != s[i]] + MIN(k = 0..j, f(i, k))

如果k!= j则[k!= j]为1,否则为0.通过顺序计算表的每一行(增加j),您可以计算O(1)中的最小值.

最终解是MIN(j = 0..25,f(n,j)).您可以通过递归跟随导致最佳解决方案的DP状态来构造相应的字符串:

const int a = 'z' - 'a' + 1;
vector<array<int, a>> f;
string s = "azbzc";

void reconstruct(int i, int j) {
  if (i == 0)
    return;
  int prev_j = min_element(begin(f[i-1]), begin(f[i-1]) + j + 1) - begin(f[i-1]);
  reconstruct(i - 1, prev_j);
  cout << (char)('a' + j);
}

int main() {
  f.resize(s.size() + 1);
  int n = s.size();
  for (int i = 0; i < n; ++i) {
    int sol = f[i][0];
    for (int j = 0; j < a; ++j) {
      sol = min(sol, f[i][j]);
      f[i+1][j] = (j != s[i] - 'a') + sol;
    }
  }
  int j = min_element(begin(f[n]), end(f[n])) - begin(f[n]);
  cout << "solution: " << f[n][j] << endl;
  reconstruct(n, j);
  cout << endl;
}

输出:

solution: 2
aabbc