Editorial for ptit027: Dãy ngoặc đúng dài nhất

Hiểu bài toán

Cho một xâu ký tự S chỉ gồm các ký tự '(' và ')'. Nhiệm vụ là tìm độ dài của xâu con liên tiếp dài nhất mà là một dãy ngoặc đúng.

Dãy ngoặc đúng được định nghĩa:

• Xâu rỗng là dãy ngoặc đúng.
• Nếu A là dãy ngoặc đúng thì (A) là dãy ngoặc đúng.
• Nếu A và B là dãy ngoặc đúng thì AB là dãy ngoặc đúng.

Ví dụ: Với S = "()(())))", dãy ngoặc đúng dài nhất là "()(())" có độ dài 6.

Các cách tiếp cận

Cách Dynamic Programming (Quy hoạch động)

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
    int t;cin>>t;
    while(t--){
    string s;
    cin>>s;
    s="  "+s;
    int maxx=0;
    vector<int>dp;
    dp.resize(s.size(),0);
    for(int i=2;i<s.size();i++)
    {
        if(s[i]=='(') {dp[i]=0;}
        else
        {
          if(s[i-1]=='('){dp[i]=dp[i-2]+2; maxx=max(dp[i],maxx);}
          else
          {
              int j=i-dp[i-1]-1;
              if (j>=0 && s[j]=='(') {dp[i]=dp[i-1]+dp[j-1]+2;maxx=max(dp[i],maxx);}
          }
        }
    }

    cout<<maxx<<endl;
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Sử dụng mảng động DP để lưu độ dài dãy ngoặc đúng kết thúc tại vị trí i.

Quy tắc cập nhật DP[i] (với S[i] là ')'):

1. Nếu S[i-1] là '(': Ta có cặp ngoặc đơn "()". DP[i] = DP[i-2] + 2.
2. Nếu S[i-1] là ')': Xem xét ký tự trước dãy ngoặc đúng kết thúc tại i-1. Gọi j = i - DP[i-1] - 1. Nếu S[j] là '(', ta có dạng "(A)B" (hoặc "(A)"). Khi đó DP[i] = DP[i-1] + DP[j-1] + 2.

Cập nhật max_length trong quá trình tính toán. Cách này xử lý được các trường hợp lồng nhau và nối tiếp nhau.

Cách Stack (Ngăn xếp)

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int maxlen = 0;
        stack<int> st;
        st.push(-1);  // base index before the valid substring starts

        for (int i = 0; i < (int)s.size(); i++) {
            if (s[i] == '(') {
                st.push(i);
            } else {
                if (!st.empty()) st.pop();
                if (!st.empty()) {
                    maxlen = max(maxlen, i - st.top());
                } else {
                    st.push(i);
                }
            }
        }

        cout << maxlen << "\n";
    }

    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Sử dụng một ngăn xếp để lưu chỉ số của các dấu ngoặc mở '('.

Luồng xử lý:

• Khởi tạo ngăn xếp với -1 (đánh dấu điểm xuất phát).
• Khi gặp '(': Push chỉ số hiện tại vào stack.
• Khi gặp ')':
  • Pop phần tử trên cùng (nếu có).
  • Nếu stack không rỗng sau khi pop: Độ dài dãy ngoặc đúng hiện tại là i - st.top(). Cập nhật max.
  • Nếu stack rỗng: Nghĩa là dãy ngoặc hiện tại không thể kéo dài thêm. Push chỉ số hiện tại i vào stack để làm mốc mới cho các dãy tiếp theo.

Cách này c cực kỳ trực quan và hiệu quả để tìm dãy ngoặc đúng liên tiếp.

Cách Two Pointers (Đếm và Reset)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        string s;
        cin >> s;
        int ans = 0;

        // Left to Right
        int open = 0, close = 0;
        for(char c : s) {
            if(c == '(') open++;
            else close++;
            if(open == close) ans = max(ans, 2 * open);
            else if(close > open) { open = 0; close = 0; }
        }

        // Right to Left
        open = 0; close = 0;
        for(int i = s.length() - 1; i >= 0; i--) {
            if(s[i] == '(') open++;
            else close++;
            if(open == close) ans = max(ans, 2 * open);
            else if(open > close) { open = 0; close = 0; }
        }

        cout << ans << endl;
    }
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là giải pháp tối ưu về bộ nhớ.

Duyệt từ trái sang phải:

• Đếm số '(' (open) và ')' (close).
• Nếu open == close: Ta có một dãy ngoặc đúng tiềm năng. Cập nhật độ dài.
• Nếu close > open: Dãy hiện tại sai, reset counters về 0.

Duyệt từ phải sang trái:

• Cần duyệt lại để bắt các trường hợp như "((()", trong đó số '(' nhiều hơn ')' mà vẫn tạo ra dãy ngoặc đúng ở cuối.
• Logic tương tự nhưng kiểm tra open > close để reset.

Cách này chỉ dùng O(1) bộ nhớ nhưng yêu cầu duyệt 2 lượt.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán yêu cầu tìm xâu con liên tiếp (contiguous substring), không phải xâu con bất kỳ (subsequence).
• Ngăn xếp là công cụ tự nhiên để kiểm tra tính đúng của ngoặc bằng cách lưu vị trí của ngoặc mở.
• Có thể giải quyết bằng quy hoạch động để xử lý các dãy ngoặc đúng lồng nhau và liền kề nhau.

Lỗi thường gặp

• Quên xử lý trường hợp dãy ngoặc đúng nằm ở cuối chuỗi khi duyệt.
• Sử dụng thuật toán tìm dãy ngoặc đúng tổng thể (toàn bộ chuỗi) thay vì tìm dãy dài nhất (có thể nằm ở bất kỳ đâu).
• Độ dài chuỗi lớn (~10^5) cần sử dụng các thuật toán O(n) và tối ưu I/O.