Tìm số lớn nhất sau tối đa K lần hoán đổi trong C++

Giới thiệu

Cho số nguyên n (dạng chuỗi) và số lần hoán đổi tối đa k. Tìm số lớn nhất có thể tạo được bằng cách hoán đổi tối đa k cặp chữ số.

Ví dụ

n = "538", k = 1

Hoán đổi 5 và 8 → "835" (lớn nhất có thể)

Thuật toán Backtracking

Thử tất cả các cặp hoán đổi có thể, giữ lại số lớn nhất. Tối ưu: chỉ hoán đổi khi chữ số sau lớn hơn chữ số trước.

Mã nguồn hoàn chỉnh

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

void findMaxNumber(string num, int k, string &maxNum) {
    if (k == 0) return;
    
    int n = num.length();
    
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (num[i] < num[j]) {
                swap(num[i], num[j]);
                
                if (num > maxNum) maxNum = num;
                
                findMaxNumber(num, k - 1, maxNum);
                
                swap(num[i], num[j]); // Backtrack
            }
        }
    }
}

int main() {
    string str = "15263";
    int k = 3;
    string maxNum = str;
    
    findMaxNumber(str, k, maxNum);
    cout << "So lon nhat sau " << k << " hoan doi: " << maxNum << endl;
    
    return 0;
}

Kết quả chạy chương trình

So lon nhat sau 3 hoan doi: 65321

Phân tích độ phức tạp

• Thời gian: O((n²)ᵏ) - rất lớn, chỉ phù hợp n, k nhỏ
• Không gian: O(k) - stack đệ quy

Tối ưu hóa: Tham lam (Greedy) O(n²)

Ở mỗi vị trí i, tìm chữ số lớn nhất ở phía sau và hoán đổi với nó.

string maxNumberGreedy(string num, int k) {
    int n = num.length();
    
    for (int i = 0; i < n - 1 && k > 0; i++) {
        // Tìm max digit từ i+1 đến cuối
        int maxPos = i;
        for (int j = i + 1; j < n; j++) {
            if (num[j] > num[maxPos]) maxPos = j;
        }
        
        if (maxPos != i) {
            swap(num[i], num[maxPos]);
            k--;
        }
    }
    return num;
}

So sánh

Kết luận

Bài toán tìm số lớn nhất sau k hoán đổi có giải pháp tham lam tối ưu O(n²). Backtracking chỉ dùng cho n,k rất nhỏ hoặc khi cần liệt kê tất cả khả năng.