আমাদের কাছে একটি স্ট্রিং আছে, ধরি str যেকোনো দৈর্ঘ্যের। কাজটি হলো দিয়ে गये স্ট্রিংকে এমনভাবে রিয়ারেঞ্জ করা যাতে ফলাফল স্ট্রিংএ দুটি একই আডজেসেন্ট ক্যারেক্টার একসাথে থাকে না।
বিভিন্ন ইনপুট আউটপুট সিনেরিও −
ইনপুট − string str = "itinn"
আউটপুট − Rearrangement of characters in a string such that no two adjacent are same is: initn.
ব্যাখ্যা − আমাদের কাছে একটি স্ট্রিং টাইপ ভেরিয়েবল আছে, ধরি str। এখন আমরা ইনপুট স্ট্রিংয়ের ক্যারেক্টারগুলো এমনভাবে রিয়ারেঞ্জ করব যাতে দুটি একই ক্যারেক্টার একই পজিশনে থাকে না অর্থাৎ 'nn' শিফট করব কারণ সেগুলো একই এবং আডজেসেন্ট। তাই চূড়ান্ত স্ট্রিং হবে 'initn'।
ইনপুট − string str = "abbaabbaa"
আউটপুট − Rearrangement of characters in a string such that no two adjacent are same is: ababababa
ব্যাখ্যা − আমাদের কাছে একটি স্ট্রিং টাইপ ভেরিয়েবল আছে, ধরি str। এখন আমরা ইনপুট স্ট্রিংয়ের ক্যারেক্টারগুলো এমনভাবে রিয়ারেঞ্জ করব যাতে দুটি একই ক্যারেক্টার একই পজিশনে থাকে না অর্থাৎ 'bb', 'aa', 'bb', 'aa' শিফট করব কারণ সেগুলো একই এবং আডজেসেন্ট। তাই চূড়ান্ত স্ট্রিং হবে 'ababababa'।
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি
স্ট্রিং টাইপ একটি ভেরিয়েবল ইনপুট নেওয়া, ধরি str এবং স্ট্রিংয়ের আকার হিসাব করে length নামক ভেরিয়েবলে স্টোর।
চেক IF length ০ হলে রিটার্ন।
Rearrangement(str, length) ফাংশনে ডেটা পাস।
Rearrangement(arr, length) ফাংশনের ভিতরে
স্ট্রিংয়ের আকার (length + 1)/2 দিয়ে সেট।
vector<int> vec(26, 0) ডিক্লেয়ার যেটি ইন্টিজার ডেটা স্টোর করবে এবং string টাইপ ptr(length, ' ')। একটি টেম্পোরারি ইন্টিজার ভেরিয়েবল ০ হিসেবে।
str traverser করার জন্য FOR লুপ। লুপের ভিতরে vec[it - 'a']++।
character টাইপ ch ভেরিয়েবল ডিক্লেয়ার এবং maximum(vec) ফাংশন কল দিয়ে সেট।
integer টাইপ total ভেরিয়েবল ডিক্লেয়ার এবং vec[ch - 'a'] দিয়ে সেট।
চেক IF total > size তবে রিটার্ন।
WHILE total লুপ। লুপের ভিতরে ptr[temp] = ch, temp = temp + 2 এবং total ১ কমাও।
vec[ch - 'a'] = 0 সেট। i ০ থেকে ২৫ পর্যন্ত FOR লুপ। লুপের ভিতরে while vec[i] > 0। temp = (temp >= length) ? 1 : temp এবং ptr[temp] = 'a' + i এবং temp = temp + 2 এবং vec[i] ১ কমাও।
ptr রিটার্ন।
char maximum(const vector<int>& vec) ফাংশনের ভিতরে
integer টাইপ high ০ এবং character টাইপ 'c' ডিক্লেয়ার।
i ০ থেকে ২৫ পর্যন্ত FOR লুপ। লুপের ভিতরে চেক IF vec[i] > high তবে high = vec[i] এবং c = 'a' + i।
c রিটার্ন।
ফলাফল প্রিন্ট।
উদাহরণ
#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
