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

मान लीजिए कि हमारे पास केवल तीन वर्ण 'ए', 'बी' और 'सी' के साथ एक स्ट्रिंग है। हम निम्नलिखित एल्गोरिथम को कितनी भी बार स्ट्रिंग पर लागू करेंगे -

s से एक गैर-रिक्त उपसर्ग का चयन करें जहां उपसर्ग के सभी वर्ण समान हों।
s से एक गैर-रिक्त प्रत्यय का चयन करें जहाँ प्रत्यय के सभी वर्ण समान हों।
उपसर्ग और प्रत्यय संयुक्त हैं।
उपसर्ग और प्रत्यय के वर्ण समान होने चाहिए।
उपसर्ग और प्रत्यय दोनों को s से हटा दें।

अंत में, हमें उपरोक्त ऑपरेशन को कितनी भी बार (संभवतः शून्य बार) करने के बाद s की न्यूनतम लंबाई ज्ञात करनी होगी।

इसलिए, यदि इनपुट s ="aabccabba" जैसा है, तो आउटपुट 3 होगा क्योंकि हम पहले उपसर्ग ="aa" और प्रत्यय ="a" का चयन कर सकते हैं, ताकि हटाने के बाद स्ट्रिंग "bccabb" हो, फिर उपसर्ग ="बी" और प्रत्यय "बीबी" का चयन करें, इसलिए हटाने के बाद स्ट्रिंग "सीसीए" है, जिसकी लंबाई 3 है।

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

s :=s के साथ एक कतार बनाएं
जबकि s> 1 और s[0] का आकार s का अंतिम तत्व है, करें
- chk :=s[0]
- जबकि s और s[0] समान हैं, करें
  - s से बायां तत्व हटाएं
- जबकि s खाली नहीं है और s का अंतिम तत्व chk के समान है, करें
  - s से अंतिम तत्व हटाएं
s का वापसी आकार

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

from collections import deque
def solve(s):
   s = deque(s)
   while len(s) > 1 and s[0] == s[-1]:
      chk = s[0]
      while s and s[0] == chk:
         s.popleft()
      while s and s[-1] == chk:
         s.pop()
   return len(s)

s = "aabccabba"
print(solve(s))

इनपुट

"aabccabba"