পাইথনে স্ট্রিং পার্টিশন করে প্রতিটি অক্ষর সর্বোচ্চ একবার আসা নিশ্চিত করার প্রোগ্রাম

ধরুন আমাদের একটি ছোট হাতের স্ট্রিং s দেওয়া আছে। আমরা স্ট্রিংটিকে যতটুকু সম্ভব পার্টিশন করতে পারি এমনভাবে যে প্রতিটি অক্ষর সর্বোচ্চ একটি পার্টিশনে থাকে। পার্টিশনগুলোর আকারগুলো একটি তালিকা হিসেবে ফেরত দিতে হবে।

উদাহরণস্বরূপ, ইনপুট s = "momoplaykae" হলে আউটপুট হবে [4, 1, 1, 4, 1], কারণ স্ট্রিংটি ভাগ হয় ["momo", "p", "l", "ayka", "e"]।

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

• count := Counter(s) (প্রতিটি অক্ষরের घटনা)
• out := [], stk := [], length := 0
• প্রতিটি char in s এর জন্য:
  • count[char] -= 1
  • length += 1
  • যখন count[char] != 0 or stk:
    • যদি count[char] != 0, তবে stk.append(char) এবং ব্রেক
    • যদি stk খালি না এবং count[stk[-1]] == 0, তবে stk.pop()
    • অন্যথায় ব্রেক
  • যদি stk খালি এবং count[char] == 0, তবে out.append(length) এবং 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.append(length)
                length = 0
        return out

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

ইনপুট

"momoplaykae"

আউটপুট

[4, 1, 1, 4, 1]