সমস্যার বর্ণনা:
শুধু 0 আর 1 সংবলিত একটা বাইনারি string দেয়া আছে, যার length দেয়া আছে n ।
এই string এ 0 আর 1 পাশাপাশি রাখা যাবে না । এজন্য যেসব স্থানে একটি 0 আর একটি 1 পাশাপাশি আছে, এমন 0 আর 1 গুলোকে রিমুভ করে দিতে হবে । এভাবে সকল পাশাপাশি থাকে 0 আর 1 কে রিমুভ করে দেবার পরে বাকি ক্যারেকটারগুলি নিয়ে নতুন string তৈরি হবে ।
একই ভাবে নতুন string যদি আবারও কোথাও একটি 0 আর একটি 1 পাশাপাশি থাকে, তবে এই প্রসেস চলতেই থাকবে, অর্থাৎ আবারও যেসব স্থানে একটি 0 আর একটি 1 পাশাপাশি আছে, এমন 0 আর 1 গুলোকে রিমুভ করে দিতে হবে - যতক্ষণ না string এ কোথাও কোন 0 আর 1 পাশাপাশি না থাকে ।
আউটপুটে দেখাতে হবে এভাবে রিমুভ করার পরে, ফাইনালি string এর মিনিমাম length কত হবে ?
Sample ইনপুট ও আউটপুটঃ
...............
Input
41100
Output
0ব্যাখ্যাঃ
1100 এ ২য় ও ৩য় পজিশনের 0 আর 1 পাশাপাশি আছে । এদেরকে রিমুভ করে দেবার পরে string থাকে ১ম 1 ও শেষ 0. এরা কাছাকাছি চলে এসে নতুন string হয় 10
আবারও 1 আর 0 পাশাপাশি আছে । তাই এদের দুইটাই রিমুভ হয়ে আর কিছুই থাকবে না । তাই আউটপুট 0.
...................
Input
501010
Output
1ব্যাখ্যাঃ
01010 তে ২য় পজিশনের 1 ও ৩য় পজিশনের 0 পাশাপাশি এবং ৪র্থ পজিশনের 1 ও ৫ম পজিশনের 0 পাশাপাশি আছে । তাই এই ৪ টা রিমুভ হবার পরে থাকে শুধু ১ম 0. তাই আউটপুট 1, কারণ এই string এর length হলো 1.
...................
Input
811101111
Output
6ব্যাখ্যাঃ
এখানে ৪র্থ পজিশনের 0 বামেও 1 আছে ও ডানেও 1 আছে । তাই ৪র্থ ও ৫ম অথবা ৩য় ও ৪র্থ পজিশনের দুইটা digit কে রিমুভ করে দিলে আর কোন 0, 1 পাশাপাশি থাকবে না । তাই আউটপুট 6.
..................
সমাধানঃ
একটু চিন্তা করে দেখলেই সহজেই প্রোবলেমটা সলভ করতে পারি । string এ যদি 0 আর 1 দুটোই থাকে তবে, যে কোন একটা 0 আর একটা 1 adjacent হবেই । কারণ অন্তত একটা 0 কে কোন না কোন 1 এর পাশে থাকবেই ।
যখন তাদের রিমুভ করব আবার যদি 0 আর 1 দুটোই থাকে, তবে আবারো নতুন adjacent তৈরী হবেই ।
যেহেতু প্রতি বার রিমুভ করার সময় একসাথে দুইটা ডিজিট রিমুভ করতে হয়, তাই আমরা দেখব মোট কত জোড়া 0 আর 1 আছে । অত জোড়াই রিমুভ করা যাবে । এজন্য 0 আর 1 এর মাঝে দেখতে হবে কোনটি কম আছে । তত জোড়া তৈরি হবে, বাকি ডিজিট গুলো থেকে যাবে ।
আশা করছি, বুঝতে পেরেছ । তাই আর বেশি ব্যাখ্যা দিলাম না । তবুও বুঝতে সমস্যা হলে কমেন্টে জানাও ।
কোডটা হবে এরকম-