สมมติว่าเรามีสตริง S ที่มีอักขระ n ตัว S มีเฉพาะตัวพิมพ์เล็กเท่านั้น เราต้องเลือกตัวเลข k ในช่วง 0 ถึง n จากนั้นเลือก k อักขระจาก S และเรียงลำดับตามลำดับใดก็ได้ ในกระบวนการนี้ อักขระที่เหลือจะไม่เปลี่ยนแปลง เราดำเนินการทั้งหมดนี้เพียงครั้งเดียว เราต้องหาค่าของ k โดยที่ S จะเรียงลำดับตามตัวอักษร
ดังนั้น หากอินพุตเป็น S ="acdb" เอาต์พุตจะเป็น 3 เนื่องจาก 'a' อยู่ที่ตำแหน่งที่ถูกต้อง และควรจัดเรียงอักขระที่เหลือใหม่
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
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
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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;
} อินพุต
"acdb"
ผลลัพธ์
3
