জাভাস্ক্রিপ্টে বাইনারি স্ট্রিংয়ে ন্যূনতম ফ্লিপ নির্ণয়

Monotonically Increasing String:

একটি '0' এবং '1' স্ট্রিং monotonically increasing হবে যদি সেটি কিছু '0' (হয় ০) দিয়ে শুরু হয় এবং তারপর কিছু '1' (হয় ০) দিয়ে শেষ হয়।

সমস্যা

আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি বাইনারি স্ট্রিং str প্রথম ও একমাত্র আর্গুমেন্ট হিসেবে নেবে।

স্ট্রিংয়ে যেকোনো '0' কে '1' বা '1' কে '0' এ ফ্লিপ করা যাবে। ফাংশনটি স্ট্রিংকে monotonically increasing বানানোর জন্য ন্যূনতম ফ্লিপের সংখ্যা ফেরত দেবে।

উদাহরণস্বরূপ, যদি ইনপুট হয় –

ইনপুট

const str = '00110';

আউটপুট

const output = 1;

আউটপুট ব্যাখ্যা

কারণ যদি শেষ '0' কে '1' এ ফ্লিপ করি, তবে স্ট্রিং হবে '00111'।

উদাহরণ

const str = '00110'; 
const countFlips = (str = '') => { 
  const map = {}; 
  const helper = (index, prev) => { 
    map[index] = map[index] || {}; 
    if (map[index][prev] !== undefined) { 
      return map[index][prev]; 
    } 
    if (index >= str.length) { 
      return 0; 
    } 
    if (prev === '0') { 
      if (str[index] === '0') { 
        map[index][prev] = Math.min(helper(index + 1, '0'), helper(index + 1, '1') + 1); 
      } else { 
        map[index][prev] = Math.min(helper(index + 1, '1'), helper(index + 1, '0') + 1); 
      } 
    } else if (str[index] === '0') { 
      map[index][prev] = helper(index + 1, '1') + 1; 
    } else { 
      map[index][prev] = helper(index + 1, '1'); 
    } 
    return map[index][prev]; 
  }; 
  return helper(0, '0'); 
}; 
console.log(countFlips(str));