C++-এ লেক্সিকোগ্রাফিক্যালি সর্বশেষ সাবস্ট্রিং (Last Substring in Lexicographical Order)

একটি স্ট্রিং s দেওয়া আছে। এর সব সাবস্ট্রিংয়ের মধ্যে লেক্সিকোগ্রাফিক্যালি সর্বশেষ (সর্বোচ্চ) সাবস্ট্রিংটি বের করতে হবে।

উদাহরণ

ইনপুট: "abbbcabbc" → আউটপুট: "cabbc"

সমাধানের পদ্ধতি (Two Pointer Approach)

1. দুটি পয়েন্টার i এবং j দিয়ে সাবস্ট্রিং তুলনা করুন।
2. k দিয়ে মিলিত প্রিফিক্স দৈর্ঘ্য ট্র্যাক করুন।
3. s[i+k] == s[j+k] হলে k++।
4. s[i+k] < s[j+k] হলে i = j, j++।
5. অন্যথায় j = j + k + 1।
6. k = 0 রিসেট করুন।
7. শেষে 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;
        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);
    }
};

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

ইনপুট

"abbbcabbc"

আউটপুট

cabbc