Tối đa hóa số bằng cách thay thế đoạn chữ số liên tiếp bằng chữ số thay thế trong C++

Cho số N (dạng chuỗi) và mảng thay thế 10 chữ số alt[0..9] cho các chữ số 0-9. Nhiệm vụ: thay thế một đoạn liên tiếp duy nhất của N bằng các chữ số thay thế tương ứng để số kết quả lớn nhất.

Ví dụ 1

Input

N = "1234", alt[] = {3,0,1,5,7,7,8,2,9,4}

Output – "1257"

Giải thích: Thay đoạn "34" → "57" (alt[3]=5, alt[4]=7). Số trở thành 1257.

Ví dụ 2

Input

N = "5183", alt[] = {3,0,1,5,7,7,8,2,9,4}

Output – "7183"

Giải thích: Thay chữ số đầu '5' → '7' (alt[5]=7). Dừng vì alt[1]=0 < 1.

Thuật toán tham lam

1. Duyệt chuỗi từ trái sang phải.
2. Tìm vị trí đầu tiên có alt[digit] > digit.
3. Từ vị trí đó, tiếp tục thay thế cho đến khi gặp chữ số có alt[digit] < digit.
4. Dừng và trả về kết quả.

Ví dụ code

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

string maximizeNumber(string str, int alt[]) {
    int n = str.size();
    for (int i = 0; i < n; i++) {
        int digit = str[i] - '0';
        if (digit < alt[digit]) {
            // Bắt đầu thay thế từ i
            int j = i;
            while (j < n && (str[j] - '0') <= alt[str[j] - '0']) {
                str[j] = '0' + alt[str[j] - '0'];
                j++;
            }
            return str; // Chỉ thay 1 đoạn liên tiếp
        }
    }
    return str; // Không thay đổi
}

int main() {
    string str = "2075";
    int alt[] = {3, 0, 1, 5, 7, 7, 8, 2, 9, 4};
    cout << maximizeNumber(str, alt) << endl;
    return 0;
}

Kết quả

2375

Giải thích: str="2075". i=0: '2', alt[2]=1 < 2 → bỏ qua. i=1: '0', alt[0]=3 > 0 → bắt đầu thay. - j=1: '0'→'3' (alt[0]=3 ≥ 0) - j=2: '7', alt[7]=2 < 7 → dừng. Kết quả: "2375".

Độ phức tạp: O(N) - duyệt chuỗi một lần.