पायथन में सूची के प्रत्येक पार्टीशन का आकार ज्ञात करने का प्रोग्राम जहां प्रत्येक अक्षर अधिकतम एक टुकड़े में आता है

मान लीजिए हमारे पास एक लोअरकेस स्ट्रिंग s है, हम s को यथासंभव अधिक से अधिक टुकड़ों में विभाजित कर सकते हैं ताकि प्रत्येक अक्षर अधिकतम एक टुकड़े में आए और पार्टीशन के आकारों को सूची के रूप में वापस करें।

उदाहरण के लिए, यदि इनपुट है s = "momoplaykae", तो आउटपुट [4, 1, 1, 4, 1] होगा, क्योंकि स्ट्रिंग ["momo", "p", "l", "ayka", "e"] में विभाजित होती है।

एल्गोरिदम

• count := s में प्रत्येक वर्ण की घटनाओं वाला मैप
• out := नई सूची, stk := खाली स्टैक, length := 0
• s के प्रत्येक char के लिए:
  • count[char]--, length++
  • जब तक count[char] != 0 या stk खाली नहीं है:
    • यदि count[char] != 0, तो char को stk में डालें और ब्रेक करें
    • यदि stk खाली नहीं है और count[stk[-1]] == 0, तो stk से पॉप करें
    • अन्यथा ब्रेक करें
  • यदि stk खाली है और count[char] == 0, तो length को out में जोड़ें और length = 0 करें
• out वापस करें

उदाहरण

from collections import Counter
class Solution:
    def solve(self, s):
        count = Counter(s)
        out = []
        stk = []
        length = 0
        for char in s:
            count[char] -= 1
            length += 1
            while count[char] != 0 or stk:
                if count[char] != 0:
                    stk.append(char)
                    break
                if stk and count[stk[-1]] == 0:
                    stk.pop()
                else:
                    break
            if not stk and count[char] == 0:
                out += [length]
                length = 0
        return out

ob = Solution()
s = "momoplaykae"
print(ob.solve(s))

इनपुट

"momoplaykae"

आउटपुट

[4, 1, 1, 4, 1]