โปรแกรม C++ หาจำนวนตัวอักษรที่ต้องจัดเรียงใหม่ให้สตริงเรียงลำดับ

คำอธิบายปัญหา

สมมติว่าเรามีสตริง S n ตัวอักษร มีแต่ตัวพิมพ์เล็ก ต้องเลือก k ในช่วง 0 ถึง n แล้วเลือก k ตัวอักษรจาก S จัดเรียงใหม่ได้อย่างไรก็ได้ ตัวอักษรที่เหลือคงที่ ทำทั้งหมด 1 ครั้ง ต้องการหา k ที่ทำให้ S เรียงลำดับตามตัวอักษร

ตัวอย่าง: S = "acdb" ผลลัพธ์คือ 3 เพราะ 'a' อยู่ตำแหน่งถูกต้อง ตัวอื่นต้องจัดใหม่

ขั้นตอนการแก้ปัญหา

n := ขนาดของ S
d := S
เรียงลำดับ d
j := 0
สำหรับ i := 0 ถึง n-1:
    ถ้า S[i] != d[i]: เพิ่ม j ขึ้น 1
คืนค่า j

ตัวอย่างโค้ด 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;
}

อินพุต

"acdb"

เอาต์พุต

3