Editorial for upword: Đếm từ viết hoa

Hiểu bài toán

Đề bài yêu cầu đếm số lượng từ HOA trong một xâu ký tự. Một từ HOA được định nghĩa là một dãy các ký tự in hoa ('A' đến 'Z') liên tiếp. Điều kiện quan trọng là hai từ HOA liên tiếp phải được ngăn cách bởi ít nhất một ký tự in thường ('a' đến 'z'). Nói cách khác, ta cần đếm số lượng các 'đoạn' ký tự in hoa, trong đó mỗi đoạn được tách biệt với các đoạn khác bằng các ký tự thường.

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

Cách Kiểm tra ranh giới (Edge Detection)

#include <stdio.h>
#include <string.h>

char s[1000000];

int main() {
    scanf("%s", s);
    int len = strlen(s);
    int cnt = 0;

    // Duyệt qua từng ký tự
    for (int i = 0; i < len; i++) {
        // Điều kiện để bắt đầu một từ HOA mới:
        // 1. Ký tự hiện tại là chữ in hoa.
        // 2. Ký tự trước đó (nếu có) là chữ in thường (hoặc không có ký tự nào - i == 0).
        if (s[i] >= 'A' && s[i] <= 'Z') {
            if (i == 0 || (s[i-1] >= 'a' && s[i-1] <= 'z')) {
                cnt++;
            }
        }
    }
    printf("%d", cnt);
    return 0;
}

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

Cách tiếp cận này dựa trên việc xác định 'điểm bắt đầu' của mỗi từ HOA. Ta duyệt qua xâu từ đầu đến cuối. Một từ HOA mới được đếm khi ta gặp một ký tự in hoa mà ngay trước nó là một ký tự in thường (hoặc nó là ký tự đầu tiên của xâu). Ví dụ: 'CongCHAnhunui...' -> 'C' (đầu xâu) -> đếm; 'H' (trước nó là 'o', 'n' - là thường) -> đếm. Phương pháp này không quan tâm đến việc từ HOA kéo dài bao lâu, chỉ cần đếm đúng số lần một từ HOA mới bắt đầu.

Cách Trạng thái (State Machine)

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

char s[1000001];

int main() {
    scanf("%s", s);
    int count = 0;
    bool inUpper = false; // Biến cờ: đang ở trong từ HOA hay không

    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            // Nếu đang ở trong từ HOA (trạng thái true), ta không đếm.
            // Nếu đang ở ngoài (trạng thái false), ta đếm và chuyển sang trạng thái true.
            if (!inUpper) {
                count++;
                inUpper = true;
            }
        } else {
            // Nếu gặp ký tự thường, chuyển về trạng thái false (đang ở ngoài từ HOA)
            inUpper = false;
        }
    }
    printf("%d", count);
    return 0;
}

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

Cách tiếp cận này sử dụng một biến boolean (cờ) để theo dõi trạng thái hiện tại của trình duyệt. Ban đầu, trạng thái là 'ngoài từ HOA' (false). Khi gặp một ký tự in hoa mà đang ở trạng thái 'ngoài', ta tăng biến đếm và chuyển trạng thái thành 'đang ở trong từ HOA' (true). Chỉ khi nào gặp ký tự thường (hoặc kết thúc xâu), trạng thái mới quay lại 'ngoài'. Điều này đảm bảo rằng một từ HOA kéo dài nhiều ký tự (ví dụ: 'CHA') chỉ được đếm đúng 1 lần.

Cách Xử lý Chuỗi Nâng cao (C++ String)

#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>

using namespace std;

int main() {
    string s;
    cin >> s;

    int count = 0;
    bool inUpper = false;

    for (char c : s) {
        if (isupper(c)) {
            if (!inUpper) {
                count++;
                inUpper = true;
            }
        } else {
            inUpper = false;
        }
    }

    cout << count << endl;
    return 0;
}

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

Đây là biến thể của phương pháp 'Trạng thái' nhưng sử dụng C++ với std::string và hàm isupper để code dễ đọc và an toàn hơn. Logic hoàn toàn tương tự: theo dõi xem chúng ta có đang ở trong một khối in hoa hay không. Nếu gặp in hoa mà không ở trong khối, tăng biến đếm và đánh dấu là đang ở trong khối. Gặp ký tự thường thì bỏ đánh dấu.

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

Bài học kinh nghiệm

• Vấn đề cốt lõi là đếm số lượng 'khối' (block) chứ không phải số lượng ký tự in hoa.
• Một khối mới bắt đầu khi một ký tự in hoa xuất hiện sau một ký tự thường (hoặc ở đầu xâu).

Lỗi thường gặp

• Đếm nhầm: Dễ biến bài toán thành đếm tất cả các ký tự in hoa, ví dụ ở xâu 'CHA' sẽ đếm được 3 thay vì 1.
• Quên xử lý ký tự thường liên tiếp: Nếu logic không đúng, các ký tự thường liên tiếp có thể làm 'reset' trạng thái không đúng cách, nhưng trong bài này điều kiện khá đơn giản.
• Độ dài xâu lớn: Cần dùng mảng tĩnh hoặc biến toàn cục (với C/C++) để tránh tràn bộ nhớ stack, hoặc dùng std::string để quản lý bộ nhớ tự động.