लेक्सिकोग्राफिकली न्यूनतम स्ट्रिंग रोटेशन

परिचय

आइए मान लें कि एक स्ट्रिंग दी गई है, हम जानते हैं कि स्ट्रिंग वर्णों का एक क्रम है। लेक्सिकोग्राफिकल रोटेशन स्ट्रिंग का घुमाव है, ताकि वर्णों को लेक्सिकोग्राफिकल क्रम में बदला जा सके।

समाधान सरल है, हम बस दी गई स्ट्रिंग को स्वयं के साथ जोड़ते हैं, फिर दूसरी सरणी में, स्ट्रिंग के सभी रोटेशन संग्रहीत किए जाते हैं। उसके बाद सरणी को आरोही क्रम में क्रमबद्ध करें, सबसे कम मान अंतिम परिणाम है।

इनपुट और आउटपुट

इनपुट: स्ट्रिंग "BCAAFAABCD"
आउटपुट: रोटेटेड स्ट्रिंग: "AABCDBCAAF"

एल्गोरिदम

minStrRotation(str)
इनपुट: दी गई स्ट्रिंग
आउटपुट: आवश्यक न्यूनतम स्ट्रिंग रोटेशन

Begin
    n := str की लंबाई
    सभी रोटेशन संग्रहीत करने के लिए strArr परिभाषित करें
    tempStr := str को str के साथ फिर से जोड़ें
    i := 0 से n तक, करें
        strArr[i] := tempStr का उपस्ट्रिंग (i से n) से
    done
    strArr को क्रमबद्ध करें
    strArr[0] लौटाएं
End

उदाहरण (C++ कोड)

#include <iostream>
#include <algorithm>
using namespace std;

string minStrRotation(string str) {
    int n = str.size();
    string strArray[n]; // str के सभी रोटेशन संग्रहीत करने के लिए सरणी
    string tempStr = str + str; // str को दो बार जोड़ें
    for (int i = 0; i < n; i++)
        strArray[i] = tempStr.substr(i, n); // iवें इंडेक्स से nवें इंडेक्स तक सबस्ट्रिंग प्राप्त करें
    sort(strArray, strArray+n);
    return strArray[0]; // पहला इंडेक्स परिणाम है
}

int main() {
    string str;
    cout << "Enter String: "; cin >> str;
    cout << "Rotated String: " << minStrRotation(str);
}

आउटपुट

Enter String: BCAAFAABCD
Rotated String: AABCDBCAAF