আমাদেরকে যে কোনো প্রদত্ত দৈর্ঘ্যের একটি স্ট্রিং 'str' দেওয়া হয়েছে। কাজটি হল অক্ষরগুলিকে এমনভাবে পুনর্বিন্যাস করা যাতে প্রদত্ত ইনপুট স্ট্রিং থেকে একটি অক্ষর যোগ বা অপসারণ না করেই সর্বাধিক সাবস্ট্রিংগুলি থাকবে যা একটি প্যালিনড্রোম স্ট্রিং হবে। প্যালিনড্রোম স্ট্রিং হল এমন একটি যেখানে অক্ষরগুলি এমনভাবে সাজানো হয় যে তারা শুরু এবং শেষ থেকে একই উচ্চারণ করে।
আসুন এর জন্য বিভিন্ন ইনপুট আউটপুট পরিস্থিতি দেখি -
ইনপুট − string str ="itnin"
আউটপুট − প্যালিনড্রোমিক সাবস্ট্রিংগুলির সংখ্যা সর্বাধিক করার জন্য স্ট্রিংটির পুনর্বিন্যাস হল:iinnt৷
ব্যাখ্যা − আমাদের একটি স্ট্রিং টাইপ ভেরিয়েবল দেওয়া হয়েছে, ধরা যাক, str। এখন আমরা একটি ইনপুট স্ট্রিং এর অক্ষরগুলিকে এমনভাবে পুনর্বিন্যাস করব যে এটি একটি সর্বাধিক প্যালিনড্রোম স্ট্রিং হবে এবং যদি এটি সম্ভব না হয় তবে এটি 'সম্ভব নয়' ফিরে আসবে। সুতরাং প্রদত্ত ইনপুট স্ট্রিং সহ আউটপুট হল ‘innt.’
ইনপুট − string str ="abaaabb"
আউটপুট − প্যালিনড্রোমিক সাবস্ট্রিংগুলির সংখ্যা সর্বাধিক করার জন্য স্ট্রিংটির পুনর্বিন্যাস হল:aaaaabbb৷
ব্যাখ্যা − আমাদের একটি স্ট্রিং টাইপ ভেরিয়েবল দেওয়া হয়েছে, ধরা যাক, str। এখন আমরা একটি ইনপুট স্ট্রিং এর অক্ষরগুলিকে এমনভাবে পুনর্বিন্যাস করব যে এটি একটি সর্বাধিক প্যালিনড্রোম স্ট্রিং হবে এবং যদি এটি সম্ভব না হয় তবে এটি 'সম্ভব নয়' ফিরে আসবে। সুতরাং প্রদত্ত ইনপুট স্ট্রিং সহ আউটপুট হল aaaaabbb’
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
স্ট্রিং টাইপের একটি ভেরিয়েবল ইনপুট করুন, ধরা যাক, str এবং একটি স্ট্রিংয়ের আকার গণনা করুন এবং এটিকে ভেরিয়েবল নামে একটি দৈর্ঘ্যে সংরক্ষণ করুন।
-
Rearr_string(str, length) ফাংশনে ডেটা পাস করুন।
-
Rearr_string(str, length)
ফাংশনের ভিতরে-
26 আকারের পূর্ণসংখ্যা ধরণের একটি অ্যারে ঘোষণা করুন, আসুন বলি, arr[26] এবং এটিকে 0 দিয়ে আরম্ভ করুন।
-
টাইপ স্ট্রিং এর একটি অস্থায়ী পরিবর্তনশীল 'টেম্প' ঘোষণা করুন।
-
i থেকে 0 পর্যন্ত লুপ শুরু করুন যতক্ষণ না i দৈর্ঘ্যের চেয়ে কম হয়। লুপের ভিতরে, arr[str[i] - 'a']++ সেট করুন।
-
i থেকে 0 থেকে i 26 এর কম না হওয়া পর্যন্ত FOR লুপ শুরু করুন। লুপের ভিতরে, j থেকে 0 থেকে j পর্যন্ত arr[i] কম না হওয়া পর্যন্ত আরেকটি লুপ FOR শুরু করুন। লুপের ভিতরে, temp + (char)(97 + i) এ temp সেট করুন।
-
রিটার্ন টেম্প।
-
-
ফলাফল প্রিন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
string Rearr_string(string str, int length){
int arr[26] = { 0 };
string temp = "";
for(int i = 0; i < length; i++){
arr[str[i] - 'a']++;
}
for(int i = 0; i < 26; i++){
for(int j = 0; j < arr[i]; j++){
temp = temp + (char)(97 + i);
}
}
return temp;
}
int main(){
string str = "itinn";
int length = str.length();
cout<<"Rearrangement of the string to maximize the number of palindromic substrings is: "<<Rearr_string(str, length);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে
Rearrangement of the string to maximize the number of palindromic substrings is: iinnt
