Python में स्ट्रिंग को संतुलित बनाने के लिए न्यूनतम डिलीशन गिनने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है जिसमें केवल दो वर्ण 's' और 't' हैं। हम s के किसी भी संख्या में वर्णों को हटाकर स्ट्रिंग को संतुलित बना सकते हैं। हम कह सकते हैं, s संतुलित है जब ऐसा कोई इंडेक्स जोड़ी (i,j) नहीं है जैसे कि i < j और s[i] = 't' और s[j] = 's'। हमें s को संतुलित बनाने के लिए आवश्यक न्यूनतम डिलीशन की संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है s = "sststtst", तो आउटपुट 2 होगा क्योंकि हम या तो, इंडेक्स 2 और 6 पर वर्ण हटा सकते हैं ("sststtst" से "sssttt"), या इंडेक्स 3 और 6 पर वर्ण हटा सकते हैं ("sststtst" से "sstttt")।

समाधान के चरण

1. cum_b := 0
2. count_a := s.count("s")
3. ans := infinity
4. s में प्रत्येक x के लिए:
   • यदि x == "s":
     • count_a := count_a - 1
     • ans := min(ans, cum_b + count_a)
   • अन्यथा:
     • cum_b := cum_b + 1
     • ans := min(ans, cum_b-1 + count_a)
5. ans वापस करें

उदाहरण

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

def solve(s):
    cum_b = 0
    count_a = s.count("s")
    ans = float("inf")
    for x in s:
        if x == "s":
            count_a -= 1
            ans = min(ans, cum_b + count_a)
        else:
            cum_b += 1
            ans = min(ans, cum_b-1 + count_a)
    return ans

s = "sststtst"
print(solve(s))

इनपुट

"sststtst"

आउटपुट

2