मान लीजिए हमारे पास एक स्ट्रिंग s है जिसमें केवल तीन वर्ण 'a', 'b', और 'c' हैं। हम स्ट्रिंग पर निम्नलिखित एल्गोरिदम को कितनी भी बार लागू कर सकते हैं:
sसे एक नॉन-खाली प्रीफिक्स चुनें जहां प्रीफिक्स के सभी वर्ण समान हों।sसे एक नॉन-खाली सफ़िक्स चुनें जहां सफ़िक्स के सभी वर्ण समान हों।- प्रीफिक्स और सफ़िक्स डिसजॉइंट हों।
- प्रीफिक्स और सफ़िक्स के वर्ण समान होने चाहिए।
sसे प्रीफिक्स और सफ़िक्स दोनों को हटा दें।
अंत में, हमें उपरोक्त ऑपरेशन को कितनी भी बार (संभवतः शून्य बार) करने के बाद s की न्यूनतम लंबाई ढूंढनी है।
उदाहरण के लिए, यदि इनपुट है s = "aabccabba", तो आउटपुट 3 होगा क्योंकि पहले हम prefix = "aa" और suffix = "a" चुन सकते हैं, तो हटाने के बाद स्ट्रिंग "bccabb" होगी, फिर prefix = "b" और suffix = "bb" चुनें, तो हटाने के बाद स्ट्रिंग "cca" होगी, जिसकी लंबाई 3 है।
समाधान के चरण
s :=sके साथ एक क्यू बनाएंwhile len(s) > 1 and s[0] == s[-1]:chk := s[0]while s and s[0] == chk:sसे बायां तत्व हटाएं
while s and s[-1] == chk:sसे अंतिम तत्व हटाएं
len(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"आउटपुट
3
