পাইথন প্রোগ্রাম - ন্যূনতম মনোটোনাস স্ট্রিং গ্রুপের সংখ্যা বের করুন

মনে করুন s একটি ছোট হাতের স্ট্রিং। আমাদের ন্যূনতম সংখ্যক সन्नিবেশ সাবস্ট্রিং বের করতে হবে যাতে s ভাগ হয়ে যায় এবং প্রতিটি সাবস্ট্রিং হয় নন-ইনক্রিজিং বা নন-ডিক্রিজিং। উদাহরণস্বরূপ, "pqqqr" নন-ডিক্রিজিং স্ট্রিং, এবং "qqqp" নন-ইনক্রিজিং স্ট্রিং।

ইনপুট s = "pqrsrqp" হলে আউটপুট হবে ২, কারণ আমরা s কে "pqrs" এবং "rqp"-এ ভাগ করতে পারি।

সমাধানের ধাপসমূহ:

• যদি s খালি হয়, তবে 0 ফেরত দিন
• last := s[0]
• direction := 1
• count := 1
• s-এ প্রতিটি char-এর জন্য:
  • যদি char > last:
    • যদি direction == 1, তবে direction := 0
    • অন্যথায় যদি direction == 2, তবে direction := 1, count := count + 1
  • অন্যথায় যদি char < last:
    • যদি direction == 1, তবে direction := 2
    • অন্যথায় যদি direction == 0, তবে direction := 1, count := count + 1
  • last := char
• count ফেরত দিন

উদাহরণ

বাস্তবায়ন:

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