पायथन में नीरस स्ट्रिंग समूहों की न्यूनतम संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक लोअरकेस स्ट्रिंग s है। हमें सन्निहित सबस्ट्रिंग की न्यूनतम संख्या ज्ञात करनी है जिसमें s को भागों में इस प्रकार विभाजित किया गया है कि प्रत्येक सबस्ट्रिंग या तो गैर-बढ़ती या गैर-घटती है। तो उदाहरण के लिए, यदि स्ट्रिंग "pqqqr" की तरह है, तो एक गैर-घटती स्ट्रिंग है, और "qqqp" एक गैर-बढ़ती स्ट्रिंग है।

इसलिए, यदि इनपुट s ="pqrsrqp" जैसा है, तो आउटपुट 2 होगा, क्योंकि हम s को "pqrs" और "rqp" की तरह तोड़ सकते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• अगर s खाली है, तो

  • वापसी 0

• अंतिम:=एस[0]

• दिशा :=1

• गिनती :=1

• एस में प्रत्येक चार के लिए, करें

  • अगर चार> आखिरी, फिर

    • अगर दिशा 1 के समान है, तो

      • दिशा :=0

    • अन्यथा जब दिशा 2 के समान हो, तब

      • दिशा :=1

      • गिनती :=गिनती + 1

  • अन्यथा जब चार <आखिरी, तब

    • अगर दिशा 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