পাইথনে ন্যূনতম সংখ্যক একঘেয়ে স্ট্রিং গ্রুপ খুঁজে বের করার প্রোগ্রাম

ধরুন আমরা একটি ছোট হাতের স্ট্রিং s আছে. আমাদের সংলগ্ন সাবস্ট্রিংগুলির ন্যূনতম সংখ্যাগুলি খুঁজে বের করতে হবে যেখানে s কে এমন অংশে বিভক্ত করা হয়েছে যাতে প্রতিটি সাবস্ট্রিং হয় অ-বৃদ্ধি হয় বা অ-হ্রায়। উদাহরণস্বরূপ, যদি স্ট্রিংটি হয় "pqqqr" একটি অ-হ্রাসমান স্ট্রিং, এবং "qqqp" একটি অ-বর্ধিত স্ট্রিং৷

সুতরাং, ইনপুট যদি s ="pqrsrqp" এর মত হয়, তাহলে আউটপুট হবে 2, কারণ আমরা "pqrs" এবং "rqp" এর মত s ভাঙ্গতে পারি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• যদি s খালি হয়, তাহলে

  • রিটার্ন 0

• শেষ :=s[0]

• দিকনির্দেশ:=1

• গণনা :=1

• প্রতিটি অক্ষরের জন্য s, করুন

  • যদি char> শেষ হয়, তাহলে

    • যদি দিকনির্দেশ 1 এর মত হয়, তাহলে

      • দিক:=0

    • অন্যথায় যখন দিকনির্দেশ 2 এর মত হয়, তখন

      • দিকনির্দেশ:=1

      • গণনা :=গণনা + 1

  • অন্যথায় যখন char

    • যদি দিকনির্দেশ 1 এর মত হয়, তাহলে

      • দিক:=2

    • অন্যথায় যখন দিকনির্দেশ 0 এর মত হয়, তখন

      • দিকনির্দেশ:=1

      • গণনা :=গণনা + 1

  • শেষ :=চার

• ফেরত গণনা

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

def solve(s):
   if not s:
      return 0

   last = s[0]
   direction = 1
   count = 1

   for char in s:
      if char > last:
         if direction == 1:
            direction = 0
         elif direction == 2:
            direction = 1
            count += 1
      elif char < last:
         if direction == 1:
            direction = 2
         elif direction == 0:
            direction = 1
            count += 1
      last = char

   return count

s = "pqrsrqp"
print(solve(s))

ইনপুট

"pqrsrqp"

আউটপুট

2