C++-এ Find Permutation: গোপন স্বাক্ষর থেকে 렉্সিকোগ্রাফিক্যালি সর্বনিম্ন পারমুটেশন খুঁজে বের করা

একটি গোপন স্বাক্ষর (signature) দেওয়া আছে যা শুধুমাত্র 'D' এবং 'I' অক্ষরগুলো থেকে গঠিত। এখানে 'D' মানে দুটি সংখ্যার মধ্যে বিস্তারিত সম্পর্ক (decreasing) এবং 'I' মানে বৃদ্ধিমান সম্পর্ক (increasing)। এই স্বাক্ষরটি ১ থেকে n পর্যন্ত унікал সংখ্যাগুলো দিয়ে একটি বিশেষ পূর্ণসংখ্যা অ্যারে থেকে তৈরি করা হয়েছে।

উদাহরণ

স্বাক্ষর "DI" কে অ্যারে [2,1,3] বা [3,1,2] দিয়ে তৈরি করা যায়, কিন্তু [3,2,4] বা [2,1,3,4] দিয়ে তৈরি করা যায় না। আমাদের কাজ হলো ১ থেকে n পর্যন্ত সংখ্যাগুলোর 렉্সিকোগ্রাফিক্যালি সর্বনিম্ন পারমুটেশন খুঁজে বের করা যা দেওয়া স্বাক্ষরটি তৈরি করতে পারে।

ইনপুট: "DI" → আউটপুট: [2,1,3] (কারণ [3,1,2] থেকেও [2,1,3] র‍্যাঙ্কে কম)।

সমাধানের পদ্ধতি (Stack ব্যবহার করে)

একটি স্ট্যাক st এবং ফলাফল সংরক্ষণের জন্য একটি ভেক্টর ret ঘোষণা করুন।
cnt = 2 আরম্ভ করুন (যদিও কোডে সরাসরি ব্যবহার করা হয়নি)।
i = 1 থেকে s.size() পর্যন্ত লুপ চালান:
- যদি s[i-1] == 'D' হয়, তবে i কে স্ট্যাকে পুশ করুন।
- অন্যথায় (অর্থাৎ 'I' হলে):
  - i কে ret-তে পুশ করুন।
  - স্ট্যাক খালি না হওয়া পর্যন্ত এর টপ এলিমেন্টগুলো ret-তে পুশ করে স্ট্যাক থেকে পপ করুন।
লুপ শেষে s.size() + 1 কে স্ট্যাকে পুশ করুন।
স্ট্যাক খালি না হওয়া পর্যন্ত এর টপ এলিমেন্টগুলো ret-তে পুশ করে পপ করুন।
ret রিটার্ন করুন।

C++ কোড উদাহরণ

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

void print_vector(vector<int> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> findPermutation(string s) {
        stack<int> st;
        vector<int> ret;
        
        for(int i = 1; i <= s.size(); i++) {
            if(s[i - 1] == 'D') {
                st.push(i);
            } else {
                ret.push_back(i);
                while(!st.empty()) {
                    ret.push_back(st.top());
                    st.pop();
                }
            }
        }
        
        st.push(s.size() + 1);
        while(!st.empty()) {
            ret.push_back(st.top());
            st.pop();
        }
        return ret;
    }
};

int main() {
    Solution ob;
    print_vector(ob.findPermutation("DIID"));
    return 0;
}

ইনপুট

"DIID"

আউটপুট

[2, 1, 3, 5, 4, ]