Sắp xếp chuỗi tùy chỉnh trong C++

Mô tả bài toán

Cho chuỗi S (không có ký tự trùng) định nghĩa thứ tự tùy chỉnh, và chuỗi T. Sắp xếp lại T sao cho thứ tự các ký tự xuất hiện trong S được giữ nguyên. Ký tự không có trong S đặt vị trí bất kỳ.

Ví dụ: S="cba", T="abcd" → "cbad" (c,b,a theo S, d tự do).

Giải thuật Đếm tần suất

1. Đếm tần suất mỗi ký tự trong T.
2. Duyệt S: thêm ký tự vào kết quả đúng số lần xuất hiện, đặt count = 0.
3. Duyệt các ký tự còn lại (count > 0): thêm vào kết quả.

Cài đặt C++

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

class Solution {
public:
    string customSortString(string S, string T) {
        vector<int> cnt(26, 0);
        for (char c : T) cnt[c - 'a']++;
        string res;
        for (char c : S) {
            res.append(cnt[c - 'a'], c);
            cnt[c - 'a'] = 0;
        }
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0) res.append(cnt[i], 'a' + i);
        }
        return res;
    }
};

int main() {
    Solution ob;
    cout << ob.customSortString("cba", "abcd"); // cbad
    return 0;
}

Độ phức tạp

• Thời gian: O(|S| + |T|).
• Không gian: O(1) (mảng 26 phần tử).