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

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

तो, यदि इनपुट s = "pqrsrqp" है, तो आउटपुट 2 होगा, क्योंकि हम 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