কনক্যাটেনেটেড স্ট্রিং স্প্লিট করে লেক্সিকোগ্রাফিক্যালি সর্বোচ্চ স্ট্রিং C++-এ

সমস্যা বিবরণ

স্ট্রিংয়ের একটি লিস্ট দেওয়া আছে। এগুলিকে লুপ আকারে কনক্যাটেনেট করতে হবে (প্রতিটি স্ট্রিং রিভার্স করা যাবে বা নয়)। লুপটি যেকোনো জায়গায় কাটে রেগুলার স্ট্রিং বানাতে হবে। সবচেয়ে লেক্সিকোগ্রাফিক্যালি বড় স্ট্রিং বের করতে হবে।

উদাহরণ

ইনপুট: ["abc", "xyz"]

সম্ভাব্য লুপস: abcxyz, abczyx, cbaxyz, cbazyx

সবচেয়ে বড়: "zyxcba" (লুপ cbazyx থেকে 'a' দিয়ে কাটা)।

অ্যালগরিদম

1. প্রথমে প্রতিটি স্ট্রিংকে তার রিভার্সের সাথে তুলনা করে লেক্সিকোগ্রাফিক্যালি বড়টি রাখুন (সেটি পরে কাটার সুবিধা দেবে)।
2. প্রতিটি স্ট্রিং i এবং এর রিভার্সভжен ওরিজিনাল দুইটি কেসে:
   • বাকি স্ট্রিংগুলো জড়িত করুন: left = strs[0..i-1], right = strs[i+1..end]।
   • বর্তমান স্ট্রিং temp এর প্রতিটি ক্যারেক্টার পজিশন k থেকে কাটা যাক: temp[k:] + right + left + temp[:k]।
   • সবচেয়ে বড়টি আপডেট করুন।

C++ বাস্তবায়ন

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

class Solution {
public:
    string ans;

    void solve(int idx, vector<string>& strs, bool rev) {
        string t = strs[idx];
        if (rev) reverse(t.begin(), t.end());
        string left, right;
        for (int i = 0; i < idx; i++) left += strs[i];
        for (int i = idx + 1; i < strs.size(); i++) right += strs[i];
        for (int k = 0; k < t.size(); k++) {
            string cand = t.substr(k) + right + left + t.substr(0, k);
            if (ans.empty() || cand > ans) ans = cand;
        }
    }

    void maximize(vector<string>& strs) {
        for (auto& s : strs) {
            string r = s;
            reverse(r.begin(), r.end());
            if (r > s) s = r;
        }
    }

    string splitLoopedString(vector<string>& strs) {
        ans = "";
        maximize(strs);
        for (int i = 0; i < strs.size(); i++) {
            solve(i, strs, false);
            solve(i, strs, true);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<string> v = {"abc", "xyz"};
    cout << ob.splitLoopedString(v); // zyxcba
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(N × L²) — N = স্ট্রিং সংখ্যা, L = গড় লেন্থ।
• স্থান জটিলতা: O(L) — টেম্পরারি স্ট্রিং।