Convert a given string into a sorted string by using minimum operations

Question

We are given an arbitrary string. Now, we can perform some operations on this string. Any letter can be transformed to any other letter. Now, we can choose any letter from the string and transform it into any other letter. This would be called as one single operation.

How can we convert a string into a string whose letters are in sorted order using minimum number of operations as described above?

All solutions, including the out-of-the-box ones are welcome!

P.S.: Here's an example-

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.

P.P.S.: As asked by some people, I am providing my own solution here-

One of the brute force solution is to exploit recursion. When we are at a certain character index of the string, we could either not change it or change it to some other character and recursively call the function with index incremented by one. If we change the character, increment the no. of operations by 1 else just pass it as is. At each step of the recursion, we can check whether the string sorted - if yes, then update the overall minimum with current count, if it's lesser than the current count.

Answer 1

This problem is equivalent to the longest increasing subsequence of your string: Clearly it is optimal to leave a maximum number of letters unchanged, and those have to form an increasing subsequence. The other direction works similarly.

While LIS can be solved in O(n log n) on general sequences, you don't even need that because you have an easier special case at hand with a small alphabet size a = 26. You can use dynamic programming to solve the problem in O(n · a):

Let f(i, j) be the optimal solution for the prefix s[0..(i-1)] that ends with letter j. We have the recurrence

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

Where [k != j] is 1 if k != j and 0 otherwise. By computing each row of the table sequentially (with increasing j), you can compute the minimum in O(1).

The final solution is MIN(j = 0..25, f(n, j)). You can construct the corresponding string by recursively following the DP states that lead to the optimal solution:

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;
}

Output:

solution: 2
aabbc