C++ में लेक्सिकोग्राफिक क्रम में अंतिम सबस्ट्रिंग (Last Substring in Lexicographical Order)

समस्या विवरण

एक स्ट्रिंग s दी गई है। लेक्सिकोग्राफिक (lexicographical) क्रम में s की अंतिम सबस्ट्रिंग (substring) ज्ञात करनी है।

उदाहरण

इनपुट

"abbbcabbc"

आउटपुट

"cabbc"

समाधान दृष्टिकोण (द्वि-सूचक - Two Pointer)

दो सूचक i और j वर्तमान सर्वश्रेष्ठ और उम्मीदवार सबस्ट्रिंग की शुरुआत दर्शाते हैं। k सामान्य उपसर्ग लंबाई है।

1. i=0, j=1, k=0 से शुरू करें।
2. जब j+k < n:
   • यदि s[i+k] == s[j+k]: k++ (सामान्य उपसर्ग बढ़ाएं)
   • यदि s[i+k] < s[j+k]: i = j; j++ (j बेहतर है)
   • अन्यथा: j = j + k + 1 (j छोड़ें)
   • k = 0 रीसेट करें
3. उत्तर: s.substr(i)

समय जटिलता: O(n)

कार्यकारी प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string lastSubstring(string s) {
        int i = 0, j = 1, k = 0;
        int n = s.size();
        while (j + k < n) {
            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);
    }
};

int main() {
    Solution ob;
    cout << ob.lastSubstring("abbbcabbc");
    return 0;
}

आउटपुट

cabbc