Problem 1 : Reorganize String

 767. Reorganize String-Leetcode, Medium

প্রবলেম টা প্রথমে একবার ভালো করে পড়ো। আমাদেরকে একটা স্ট্রিং দেয়া আছে, এই স্ট্রিং কে এমন অভাবে রি-অর্গানাইজ করতে হবে যেনো পাশাপাশি দুইটা ক্যারেক্টার সেইম না হয়।

একটা উদাহরন দিই,
S = "aab", re-organize = "aba"
S = "aaab", we can't re-organize this string

এপ্রোচঃ

প্রব্লেম টা অনেক ভাবে সলভ করা যায়, প্রব্লেম টা একটু আধটু বুঝলেই হইতো এতোক্ষণে ধারনা হয়ে গেছে প্রত্যেকটা ক্যারেক্টারের ফ্রিকোয়েন্সি নিয়ে আমাদের কিছু কাজ করা লাগবে।  হ্যা, আমাদের প্রথম কাজ আসলে এটাই। 

তার আগে দেখি কখন আমরা স্ট্রিং'টাকে রি-অর্গানাইজ করতে পারবো না। 

ধরি, স্ট্রিংয়ের প্রত্যেকটা ক্যারেক্টরের ফ্রিকোয়েন্সী আমরা বের করে ফেলছি, হ্যাশ ম্যাপ অথবা এরে/ভেক্টরের মাধ্যমে এটা খুব সহজে করা যাবে। 

এখন, যে ক্যারেক্টর এর ফ্রিকোয়েন্সি সর্বোচ্চ সেটা যদি টোটাল স্ট্রিং এর লেন্থ এর অর্ধেক এর বেশি হয় তাহলে আমরা এটাকে রি-অর্গানাইজ করতে পারবো না। 

কেনো?  কারন কোনো না কোনো পাশি দুইটা ক্যারেক্টার একই রকম হয়ে যাবেই। 

এখন আসি, এটা কেনো গ্রিডি প্রব্লেম? 

এইপ্রব্লেম টা যেহেতু অনেকভাবে সলভ করা যায়, সবচেয়ে সহজ উপায় যেটা হচ্ছে,  যেটা ক্যারেক্টর এর ফ্রিকোয়েন্সি সর্বোচ্চ তাকে এন্সার (ans) স্ট্রিং এর ইভেন পজিশন গুলাতে বসিয়ে দেয়া, এতে করে তাদেরকে হ্যান্ডেল করাটা খুব সহজ। গ্রিডি হওয়ার এটা একটা কারন। 

উদাহরণ সহ দেখি৷ 

string s="vvvlo";

 ফ্রিকোয়েন্সি ক্যাল্কুলেশন,

 ['v']=3, ['l'] = 1, ['o'] = 1;

string ans = _ _ _ _ _ ( প্রথম থেকে পজিশন ০ ১ ২ ৩ ৪)

                ans = v _ v _ v _(ম্যাক্সিমাম ফ্রিকোয়েন্সি 'v', কে ইভেন পজিশনে(০,২,৪) রেখে দিলাম) 

এরপর যদি পজিশন স্ট্রিং এর লেন্থ ছাড়িয়ে গেছে, তাহলে এখন আবার ঐটা(pos) কে ১ করে দিবো, যাতে ১ থেকে odd পজিশন গুলা এখন ফিল হয়ে যায়।

                ans = vlvov,এটা আমাদের এন্সার। (বিজোড় পজিশন গুলা বাকি ক্যারেক্টার দিয়ে ফিল করে দিলাম) 

এখোনোও বুঝতে সমস্যা হইলে কোড।