Tạo số nhỏ nhất bằng tối đa một lần hoán đổi chữ số C++

Mô tả bài toán

Cho số nguyên dương. Hoán đổi tối đa một cặp chữ số để tạo số nhỏ nhất có thể (không cho phép số 0 dẫn đầu).

Ví dụ

n=63519 → Output: 36519 (hoán đổi 6 và 3).

Giải thuật

• Cách 1 O(L²): Thử mọi cặp hoán đổi, lấy min (L = số chữ số).
• Cách 2 O(L): Mảng aux[i] = chỉ số chữ số nhỏ nhất bên phải i. Duyệt từ trái: tại i=0 tìm chữ số nhỏ nhất ≠0 bên phải; i>0 tìm chữ số nhỏ nhất < arr[i]. Hoán đổi cặp đầu tiên tìm được.

Mã nguồn C++ (Cách 2)

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

int findSmallestNumSwapDig(int N) {
    string s = to_string(N);
    int n = s.size();
    vector aux(n, -1);
    int right = n-1;
    for (int i=n-2; i>=1; i--) {
        if (s[i] >= s[right]) aux[i] = right;
        else {
            if (s[i]==s[i+1]) aux[i]=right;
            else { aux[i]=-1; right=i; }
        }
    }
    int small = -1;
    for (int i=1; i

The smallest number created by swapping one digit is 192756