मान लीजिए एक स्ट्रिंग S है। S के सभी अक्षर लोअरकेस में हैं। फिर, हम कितनी भी चालें बना सकते हैं।
यहां, प्रत्येक चाल में, हम पहले K अक्षरों में से एक को चुनते हैं, उसे हटाते हैं, और उसे स्ट्रिंग के अंत में रखते हैं। हमें किसी भी संख्या में चालों के बाद लेक्सिकोग्राफिकली सबसे छोटी स्ट्रिंग ढूंढनी है।
उदाहरण के लिए, यदि इनपुट "cabaa" है और K = 3, तो आउटपुट "aaabc" होगा।
हल करने का दृष्टिकोण
मुख्य अंतर्दृष्टि: यदि K > 1, तो हम स्ट्रिंग को पूरी तरह से सॉर्ट कर सकते हैं। यदि K = 1, तो हम केवल रोटेट कर सकते हैं।
यदि K > 1: स्ट्रिंग को सॉर्ट करें और वापस करें
यदि K = 1: सभी n रोटेशन आजमाएं और न्यूनतम वापस करें
उदाहरण
#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));
return 0;
}
इनपुट
"cabaa", 3
आउटपुट
aaabc
