Số lớn nhất nhỏ hơn N bằng 1 lần hoán vị C++

Cho số N (chuỗi). Hoán vị 1 cặp chữ số để được số lớn nhất có thể nhưng vẫn nhỏ hơn N.

Ví dụ

N=54624 → Hoán vị 6 (vị trí 2) và 4 (vị trí 4) → 54426

Thuật toán

• Từ phải sang trái, tìm i đầu tiên sao cho s[i] > s[i+1] (điểm giảm).
• Từ phải sang trái, tìm j lớn nhất sao cho s[j] < s[i] (và s[j] lớn nhất có thể).
• Hoán vị s[i] và s[j].
• Nếu không tìm thấy i → trả về -1.

Triển khai C++

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

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

    int j = n - 1;
    while (s[j] >= s[i] || (j > i+1 && s[j] == s[j-1])) j--;
    swap(s[i], s[j]);
    return s;
}

int main() {
    cout << largestSmallerOneSwap("54624") << endl; // 54426
    return 0;
}

Kết quả

54426