Giả sử chúng ta có một chuỗi S với n ký tự. S chỉ chứa các chữ cái thường. Chúng ta phải chọn một số k trong phạm vi từ 0 đến n, sau đó chọn k ký tự từ S và hoán vị chúng theo thứ tự bất kỳ. Trong quá trình này, các ký tự còn lại sẽ không thay đổi. Chúng tôi thực hiện toàn bộ hoạt động này chính xác một lần. Chúng ta phải tìm giá trị của k để S được sắp xếp theo thứ tự bảng chữ cái.
Vì vậy, nếu đầu vào là S ="acdb", thì đầu ra sẽ là 3, vì 'a' ở đúng vị trí và các ký tự còn lại sẽ được sắp xếp lại.
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
n := size of S d := S sort the array d j := 0 for initialize i := 0, when i < n, update (increase i by 1), do: if S[i] is not equal to d[i], then: (increase j by 1) return j
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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
"acdb"
Đầu ra
3