स्ट्रिंग बैलेंस है अगर हर '(' के लिए दो कंसेक्यूटिव '))' हों। मिनिमम इंसर्शन्स (ओपनिंग/क्लोजिंग) काउंट करें।
एल्गोरिदम
o= अनमैच्ड ओपनिंग काउंट,ret= इंसर्शन्स काउंट।- स्ट्रिंग स्कैन करें: '(' मिले तो
o++। - ')' मिले: अगर अगला भी ')' है तो पेयर प्रोसेस करें (
o--याret++अगर o=0)। - सिंगल ')' मिले:
ret++औरo--याret++। - अंत में
ret + 2*oरिटर्न करें (बचे हुए ओपनिंग के लिए दो-दो क्लोजिंग)।
उदाहरण कोड
def solve(s):
o = 0
n = len(s)
ret = 0
i = 0
while i < n:
if s[i] == '(':
o += 1
else:
if i + 1 < n and s[i + 1] == ')':
if not o:
ret += 1
else:
o -= 1
i += 1
else:
ret += 1
if not o:
ret += 1
else:
o -= 1
i += 1
return ret + 2 * o
# टेस्ट: s="(())))))" -> आउटपुट: 3
इनपुट/आउटपुट
इनपुट: "(())))))"
आउटपुट: 3
