मान लीजिए कि हमारे पास स्ट्रिंग के रूप में s है, हमें लेक्सिकोग्राफ़िक क्रम में s का अंतिम विकल्प खोजना होगा।
इसलिए, यदि इनपुट "abbbcabbc" जैसा है, तो आउटपुट "cabbc" होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
मैं:=0, जे:=1, के:=0
-
जबकि j + k
-
यदि s[i + k], s[j + k] के समान है, तो -
-
(के द्वारा 1 बढ़ाएँ)
-
निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं
-
-
अगर s[i + k]
-
मैं :=जे
-
(जम्मू को 1 से बढ़ाएं)
-
-
अन्यथा
-
जे:=जे + के + 1
-
-
कश्मीर:=0
-
इंडेक्स i से अंत तक s का रिटर्न सबस्ट्रिंग
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string lastSubstring(string s) {
int i = 0;
int j = 1;
int k = 0;
while(j + k < s.size()){
if(s[i + k] == s[j + k]) {
k++;
continue;
}
if(s[i + k] < s[j + k]){
i = j;
j++;
}else{
j = j + k + 1;
}
k = 0;
}
return s.substr(i, s.size() - i);
}
};
main(){
Solution ob;
cout << (ob.lastSubstring("abbbcabbc"));
} इनपुट
"abbbcabbc"
आउटपुट
cabbc