মনে করুন একটি বাইনারি স্ট্রিং আছে। আমরা নিচের অপারেশনগুলো যেকোনো সংখ্যক বার প্রয়োগ করতে পারি:
যদি স্ট্রিং-এ "00" সাবস্ট্রিং থাকে, তবে এটিকে "10"-এ রিপ্লেস করতে পারি।
যদি স্ট্রিং-এ "10" সাবস্ট্রিং থাকে, তবে এটিকে "01"-এ রিপ্লেস করতে পারি।
তবে আমাদের যেকোনো সংখ্যক অপারেশনের পর সংখ্যাসূচক ভ্যালু ভিত্তিক সর্বোচ্চ বাইনারি স্ট্রিং বের করতে হবে।
যেমন, ইনপুট s = "001100" হলে, আউটপুট হবে 111011, কারণ আমরা এভাবে রূপান্তর করতে পারি: (00)1100 → 101(10)0 → 1010(10) → 10(10)01 → 100(10)1 → 1(00)011 → 111011।
সমাধান পদ্ধতি
এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:
- length := s-এর সাইজ
- zeros := s-এ '0'-এর সংখ্যা
- যদি zeros < 2 হয়, তবে
- s রিটার্ন করুন
- s := s-এর বাম পাশ থেকে সব '1' রিমুভ করুন (lstrip)
- leading_ones := length - s-এর সাইজ
- leading_ones := leading_ones + zeros - 1
- trailing_ones := length - leading_ones - 1
- answer_left := leading_ones সংখ্যক '1'
- answer_right := trailing_ones সংখ্যক '1'
- answer_left + '0' + answer_right কনক্যাটেনেট করে রিটার্ন করুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:
def solve(s): length = len(s) zeros = s.count('0') if zeros < 2: return s s = s.lstrip('1') leading_ones = length - len(s) leading_ones += zeros - 1 trailing_ones = length - leading_ones - 1 answer_left = '1' * leading_ones answer_right = '1' * trailing_ones return ''.join([answer_left, '0', answer_right]) s = "001100" print(solve(s))ইনপুট
"001100"
আউটপুট
111011
