Hàng đợi có trật tự trong C++

Cho chuỗi S, mỗi bước chọn một trong K ký tự đầu, đưa về cuối. Tìm chuỗi nhỏ nhất theo thứ tự từ điển sau số bước bất kỳ.

Ví dụ: S="cabaa", K=3 → "aaabc".

Giải thuật

1. Nếu K > 1: có thể sắp xếp hoàn toàn chuỗi → trả về chuỗi đã sort.
2. Nếu K = 1: chỉ có thể xoay vòng chuỗi. Thử tất cả n lần xoay, lấy chuỗi nhỏ nhất.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string orderlyQueue(string S, int K) {
        if(K > 1){
            sort(S.begin(), S.end());
            return S;
        }
        string ret = S;
        int n = S.size();
        for(int i = 1; i < n; i++){
            S = S.substr(1) + S.substr(0, 1);
            if(S < ret) ret = S;
        }
        return ret;
    }
};
int main(){
    Solution ob;
    cout << (ob.orderlyQueue("cabaa", 3));
}

Đầu vào

"cabaa", 3

Đầu ra

aaabc