केवल 'A' और 'B' से बनी स्ट्रिंग s दी गई है। न्यूनतम कितने वर्ण हटाएं ताकि सभी 'A' सभी 'B' से पहले आ जाएं (यानी स्ट्रिंग A...AB...B रूप में हो)।
उदाहरण
इनपुट: S = "AABAABB"
आउटपुट: 1
व्याख्या: अंतिम 'A' हटाएं → "AABBBB"।
एल्गोरिदम (प्रीफिक्स-सफिक्स काउंट)
a_right= स्ट्रिंग में कुल 'A' की संख्या।b_left = 0,ans = a_right(सभी A हटाने का विकल्प)।- प्रत्येक वर्ण
cके लिए (बाएं से दाएं):- यदि
c == 'A':a_right -= 1(यह A अब बाएं भाग में है)। - अन्यथा (
'B'):b_left += 1(यह B बाएं भाग में है, इसे हटाना होगा)। ans = min(ans, a_right + b_left)(दाएं के A + बाएं के B = कुल डिलीशन)।
- यदि
ansवापस करें।
पायथन कार्यान्वयन
class Solution:
def solve(self, s):
a_right = s.count("A")
b_left = 0
ans = a_right
for c in s:
if c == "A":
a_right -= 1
else:
b_left += 1
ans = min(ans, a_right + b_left)
return ans
# परीक्षण
ob = Solution()
print(ob.solve("AABAABB")) # 1
print(ob.solve("BBBB")) # 0
print(ob.solve("AAAA")) # 0
print(ob.solve("BBA")) # 1 (पहले दो B हटाएं या अंतिम A हटाएं)
समय जटिलता
- O(n) समय, O(1) स्थान।
- एक पास, स्थिर अतिरिक्त मेमोरी।
व्याख्या
हम विभाजन बिंदु पर विचार करते हैं: बाएं भाग में केवल 'A' होंगे (बाएं के 'B' हटाए जाएंगे), दाएं भाग में केवल 'B' होंगे (दाएं के 'A' हटाए जाएंगे)। प्रत्येक संभावित विभाजन के लिए डिलीशन की गणना करके न्यूनतम लेते हैं।
