Minimum Bracket Addition in C++

สมมติว่าเรามีสตริง s ที่มีแต่ '(' และ ')' เราต้องหาจำนวนวงเล็บน้อยที่สุดที่ต้องแทรกเพื่อทำให้สตริงสมดุล (balanced)

เช่น หากอินพุตคือ "(()))(" ผลลัพธ์จะเป็น 2 เนื่องจาก "(()))(" สามารถทำให้สมดุลได้เป็น "((()))()"

ขั้นตอนการแก้ปัญหา

• ตัวแปร o = จำนวน '(' ที่ยังไม่จับคู่, cnt = จำนวน ')' ที่เกิน
• วนอ่านตัวอักษรใน s:
  • ถ้า '(' เพิ่ม o
  • ถ้า ')' และ o > 0: ลด o (จับคู่ได้)
  • ถ้า ')' และ o == 0: เพิ่ม cnt (')' เกิน)
• คืนค่า cnt + o (จำนวนวงเล็บที่ต้องเพิ่มทั้งหมด)

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(string s) {
        int o = 0, cnt = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') o++;
            else { if (o) o--; else cnt++; }
        }
        return cnt + o;
    }
};

int main() {
    Solution ob;
    cout << (ob.solve("(()))("));
}

อินพุต

"(()))("

เอาต์พุต

2