Số lớn hơn tiếp theo bằng một lần hoán vị chữ số C++

Cho số n (dạng chuỗi). Hoán vị đúng 1 cặp chữ số để được số lớn hơn n nhất có thể (next permutation với 1 swap).

Ví dụ

12345 → hoán vị 4 và 5 → 12354

Thuật toán

• Tìm từ phải sang trái chỉ số i đầu tiên sao cho s[i] < s[i+1] (điểm giảm).
• Tìm từ phải sang trái chỉ số j đầu tiên sao cho s[j] > s[i].
• Hoán vị s[i] và s[j].
• Đảo ngược đoạn sau i (để có số nhỏ nhất lớn hơn).

Code gốc chỉ swap 1 cặp, chưa đảo đoạn sau → không tối ưu cho mọi trường hợp. Dưới đây là thuật toán chuẩn next_permutation.

Triển khai C++ chuẩn

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

string nextHigherOneSwap(string num) {
    int n = num.size();
    int i = n - 2;
    while (i >= 0 && num[i] >= num[i+1]) i--;
    if (i < 0) return "-1";

    int j = n - 1;
    while (num[j] <= num[i]) j--;
    swap(num[i], num[j]);
    reverse(num.begin() + i + 1, num.end());
    return num;
}

int main() {
    string s = "12345";
    cout << nextHigherOneSwap(s) << endl; // 12354
    return 0;
}

Kết quả

12354