HSG12 Hải Phòng 2026 - Xâu cân bằng

Xem dạng PDF

Gửi bài giải

Điểm: 11,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Những ngày đầu tiên làm quen sử dụng máy vi tính, Bình luyện tập gõ các ký tự chữ cái latin 'A' – 'Z'; 'a' – 'z' và ký tự số '0' – '9'. Bình gọi một dãy có số lượng chữ cái bằng với số lượng chữ số là một "xâu cân bằng". Mỗi ngày luyện tập, Bình tò mò muốn biết ở trong chuỗi ký tự đã gõ, đoạn dài nhất là "xâu cân bằng" có bao nhiêu ký tự?

Yêu cầu: Cho dãy ký tự ~S~ chỉ gồm các chữ cái latin 'A' – 'Z'; 'a' – 'z' và ký tự chữ số '0' – '9'. Tìm đoạn dài nhất trong ~S~ là "xâu cân bằng".

Input

Ở dòng đầu tiên là dãy ký tự ~S~ có độ dài tối đa ~10^4~.

Output

Ghi ra một số là số lượng ký tự của đoạn dài nhất là "xâu cân bằng" trong dãy ký tự ~S~. Nếu không tồn tại "xâu cân bằng" thì ghi ra số 0.

Scoring

Subtask Điểm Ràng buộc
1 ~80\%~ Dữ liệu vào có ~S~ dài tối đa ~10^2~ ký tự.
2 ~20\%~ Không có giới hạn gì thêm.

Sample Input 1

AbCde56f7

Sample Output 1

6

Notes

Xâu cân bằng dài nhất có ~6~ ký tự là đoạn "de56f7".


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -1
    missmphuog  đã bình luận lúc 2, Tháng 11, 2026, 10:08
    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        string s;
        cin >> s;
        int n = s.size();
        int ans = 0, sum = 0;
        vector<int> first(2 * n + 1, -1);
    
        first[n] = 0;
    
        for (int i = 0; i < n; i++) {
            if (s[i] >= '0' && s[i] <= '9')
                sum--;
            else
                sum++;
    
            if (first[sum + n] == -1)
                first[sum + n] = i + 1;
            else
                ans = max(ans, i + 1 - first[sum + n]);
        }
        cout << ans;
        return 0;
    }