คิวที่เรียงลำดับใน C++ (Orderly Queue)

คำอธิบายปัญหา

ให้สตริง S ตัวพิมพ์เล็ก ในแต่ละการเคลื่อนย้าย เลือก 1 ใน K ตัวแรก ย้ายไปท้าย สตริง หาสตริง lexicographically smallest ที่เป็นไปได้

ตัวอย่าง

S = "cabaa", K = 3 → Output: "aaabc"

ข้อสังเกตสำคัญ

• K = 1: สามารถ rotate ได้อย่างเดียว → หา rotation ที่เล็กที่สุด
• K > 1: สามารถสลับตัวอักษรได้ทุกคู่ (bubble sort ได้) → คำตอบคือ sorted string

เหตุผล K>1 สามารถเรียงได้

ด้วย K≥2 สามารถย้ายตัวอักษรตัวใดตัวหนึ่งไปตำแหน่งไหนก็ได้โดยการ rotate และสลับ ทำให้เรียงลำดับได้สมบูรณ์

ตัวอย่างโค้ด 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