আমাদের একটি স্ট্রিং দেওয়া হয়েছে, ধরা যাক, যে কোনো প্রদত্ত দৈর্ঘ্যের str। কাজটি হল প্রদত্ত স্ট্রিংটিকে এমনভাবে পুনর্বিন্যাস করা যাতে ফলস্বরূপ স্ট্রিংটিতে একই সংলগ্ন অক্ষরগুলি একসাথে সাজানো না থাকে৷
আসুন এর জন্য বিভিন্ন ইনপুট আউটপুট পরিস্থিতি দেখি -
ইনপুট − string str ="itnn"
আউটপুট − একটি স্ট্রিং-এ অক্ষরগুলির পুনর্বিন্যাস যাতে কোনও দুটি সন্নিহিত একই না হয়:initn৷
ব্যাখ্যা − আমাদের একটি স্ট্রিং টাইপ ভেরিয়েবল দেওয়া হয়েছে, ধরা যাক, str। এখন আমরা একটি ইনপুট স্ট্রিং-এর অক্ষরগুলিকে এমনভাবে পুনর্বিন্যাস করব যাতে একই অবস্থানে কোনও দুটি একই অক্ষর না ঘটে অর্থাৎ 'nn' স্থানান্তরিত করা হয় কারণ তারা একই এবং একে অপরের সংলগ্ন। তাই চূড়ান্ত স্ট্রিং হবে 'initn'৷
৷ইনপুট − string str ="abbaabbaa"
আউটপুট − একটি স্ট্রিং-এ অক্ষরগুলির পুনর্বিন্যাস যাতে কোনও দুটি সন্নিহিত একই না হয়:ababababa
ব্যাখ্যা − আমাদের একটি স্ট্রিং টাইপ ভেরিয়েবল দেওয়া হয়েছে, ধরা যাক, str। এখন আমরা একটি ইনপুট স্ট্রিং-এর অক্ষরগুলিকে এমনভাবে পুনর্বিন্যাস করব যাতে একই অবস্থানে কোনও দুটি একই অক্ষর না ঘটে যেমন 'bb', 'aa', 'bb', 'aa' স্থানান্তরিত করা কারণ তারা একই এবং প্রতিটির সংলগ্ন। অন্যান্য সুতরাং চূড়ান্ত স্ট্রিং হবে 'আবাবাবা'৷
৷নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
স্ট্রিং টাইপের একটি ভেরিয়েবল ইনপুট করুন, ধরা যাক, str এবং একটি স্ট্রিংয়ের আকার গণনা করুন এবং এটিকে ভেরিয়েবল নামে একটি দৈর্ঘ্যে সংরক্ষণ করুন।
-
চেক করুন যদি দৈর্ঘ্য 0 হয় তারপরে ফিরে যান।
-
পুনঃবিন্যাস (str, length) ফাংশনে ডেটা পাস করুন।
-
ফাংশনের ভিতরে পুনঃবিন্যাস(arr, length)
-
(দৈর্ঘ্য + 1)/2 দিয়ে একটি স্ট্রিংয়ের আকার সেট করুন।
-
একটি ভেক্টর টাইপ ভেরিয়েবলকে vec(26, 0) হিসাবে ঘোষণা করুন যা পূর্ণসংখ্যা টাইপ ডেটা এবং স্ট্রিং টাইপের একটি ptr ptr(দৈর্ঘ্য, ‘) হিসাবে সংরক্ষণ করবে। 0 হিসাবে পূর্ণসংখ্যার একটি অস্থায়ী পরিবর্তনশীল।
-
এটির মাধ্যমে str পুনরুক্তি করতে FOR লুপ শুরু করুন। লুপের ভিতরে, vec[it - 'a']++ সেট করুন।
-
ch হিসাবে একটি ক্যারেক্টার টাইপ ভেরিয়েবল তৈরি করুন এবং সর্বোচ্চ(vec) ফাংশনে কল দিয়ে সেট করুন।
-
একটি পূর্ণসংখ্যা টাইপ ভেরিয়েবলকে মোট হিসাবে ঘোষণা করুন এবং এটিকে vec[ch - 'a'] দিয়ে সেট করুন।
-
চেক করুন যদি মোট আকারের চেয়ে বড় হয় তারপরে ফেরত দিন।
-
মোট থাকাকালীন লুপ শুরু করুন তারপর ptr[temp] কে ch এ সেট করুন, temp + 2 এ সেট করুন এবং মোট 1 দ্বারা হ্রাস করুন।
-
vec[ch - 'a'] 0 এ সেট করুন। স্টার্ট লুপ FOR i থেকে 0 থেকে i 26 এর কম না হওয়া পর্যন্ত। লুপের ভিতরে, যখন vec[i] 0-এর বেশি হয় তখন শুরু করুন। temp সেট করুন (temp> =length)? 1 :temp এবং ptr[temp] থেকে 'a' + i এবং temp থেকে temp + 2 এবং vec[i] 1 দ্বারা হ্রাস করুন।
-
ptr
ফেরত দিন
-
-
ফাংশনের ভিতরে char সর্বোচ্চ(const ভেক্টর
&vec) -
একটি পূর্ণসংখ্যা টাইপ ভেরিয়েবলকে উচ্চ থেকে 0 এবং অক্ষর টাইপ ভেরিয়েবলকে 'c' হিসাবে ঘোষণা করুন
-
i থেকে 0 থেকে i 26-এর কম না হওয়া পর্যন্ত FOR লুপ শুরু করুন। লুপের ভিতরে, IF vec[i] উচ্চ থেকে কম তা পরীক্ষা করুন তারপর vec[i] এবং c তে 'a' + i তে সেট করুন।
-
সি
রিটার্ন করুন
-
-
ফলাফল প্রিন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
char maximum(const vector<int>& vec){
int high = 0;
char c;
for(int i = 0; i < 26; i++){
if(vec[i] > high){
high = vec[i];
c = 'a' + i;
}
}
return c;
}
string Rearrangement(string str, int length){
int size = (length + 1) / 2;
vector<int> vec(26, 0);
string ptr(length, ' ');
int temp = 0;
for(auto it : str){
vec[it - 'a']++;
}
char ch = maximum(vec);
int total = vec[ch - 'a'];
if(total > size){
return "";
}
while(total){
ptr[temp] = ch;
temp = temp + 2;
total--;
}
vec[ch - 'a'] = 0;
for(int i = 0; i < 26; i++){
while (vec[i] > 0){
temp = (temp >= length) ? 1 : temp;
ptr[temp] = 'a' + i;
temp = temp + 2;
vec[i]--;
}
}
return ptr;
}
int main(){
string str = "itinn";
int length = str.length();
if(length == 0){
cout<<"Please enter a valid string";
}
string count = Rearrangement(str, length);
if(count == ""){
cout<<"Please enter a valid string";
}
else{
cout<<"Rearrangement of characters in a string such that no two adjacent are same is: "<<count;
}
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট তৈরি করবে
Rearrangement of characters in a string such that no two adjacent are same is: initn
