Chương trình tìm số lần chèn tối thiểu để cân bằng chuỗi ngoặc bằng Python

Cho chuỗi s chỉ chứa '(' và ')'. Chuỗi cân bằng khi: mỗi '(' có hai ')' liên tiếp ngay sau; '(' phải trước '))'. Ví dụ: "())", "())(())))" cân bằng; ")()", "()))" không. Tìm số ngoặc cần chèn để cân bằng.

Ví dụ: s="(())))))" → output 3 (cần thêm '(' để thành "(())(())(())").

Thuật toán

• o=0 (số '(' chờ), ret=0, i=0, n=len(s)
• While i < n:
  • Nếu s[i]=='(' : o += 1
  • Ngược lại (s[i]==')'):
    • Nếu i+1
    • Không có ')' tiếp theo: ret+=1; nếu o==0: ret+=1; else: o-=1
  • i += 1
• Return ret + 2*o

Code Python

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 = "(())))))"
print(solve(s))

Input

"(())))))"

Output

3