Chương trình C++ đếm số ký tự cần sắp xếp lại để chuỗi theo thứ tự bảng chữ cái

Cho chuỗi S độ dài n (chữ thường). Chọn k ký tự, hoán vị chúng tùy ý, phần còn lại giữ nguyên. Sau một lần thao tác, S phải được sắp xếp tăng dần. Tìm k nhỏ nhất.

Ví dụ

Với S="acdb", đầu ra 3. 'a' đúng chỗ, 3 ký tự còn lại sắp xếp lại.

Giải thuật

Tạo bản sao d của S và sắp xếp. Đếm số vị trí i mà S[i] != d[i]. Đó chính là k nhỏ nhất (các ký tự sai vị trí phải di chuyển).

Mã C++

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

int solve(string S) {
    int n = S.size();
    string d = S;
    sort(d.begin(), d.end());
    int j = 0;
    for (int i = 0; i < n; i++)
        if (S[i] != d[i]) j++;
    return j;
}

int main() {
    string S = "acdb";
    cout << solve(S) << endl;
}

Đầu vào / Đầu ra

Input: "acdb"
Output: 3