Hiểu bài toán

Bài toán yêu cầu tìm số lớn nhất trong một xâu ký tự. Xâu đầu vào chứa các ký tự chữ cái và chữ số, độ dài không quá 1000. Các số trong xâu được định nghĩa bởi các chuỗi ký tự số liên tiếp. Chúng ta cần trích xuất tất cả các số, so sánh chúng và trả về số lớn nhất. Ví dụ: với xâu 'Abc1234ef99gH0', các số là 1234, 99 và 0, số lớn nhất là 1234.

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

Cách Xử lý số học trực tiếp (Integer Accumulation)

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

int main() {
    string s;
    getline(cin, s);
    long long cur = 0, mx = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            cur = cur * 10 + (s[i] - '0');
        } else {
            mx = max(mx, cur);
            cur = 0;
        }
    }
    mx = max(mx, cur);
    cout << mx;
    return 0;
}

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

Biến cur dùng để lưu số đang đọc được, biến mx lưu số lớn nhất tìm được. Duyệt từng ký tự trong xâu: Nếu là chữ số, cập nhật cur = cur * 10 + value. Nếu là ký tự đặc biệt, so sánh cur với mx và reset cur về 0. Ở cuối vòng lặp, so sánh lại một lần nữa để xử lý số nằm ở cuối xâu. Cách này hiệu quả nhưng cần lưu ý giới hạn giá trị của long long (khoảng 10^18) và độ dài số trong xâu.

Cách Xử lý chuỗi số (String Manipulation)

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

bool cmp(string a, string b) {
    if (a.length() != b.length()) return a.length() > b.length();
    return a > b;
}

int main() {
    string s;
    cin >> s;
    string c = "";
    string m = "";
    for (int i = 0; i < s.length(); i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            c += s[i];
        } else {
            if (c != "") {
                if (m == "" || cmp(c, m)) m = c;
                c = "";
            }
        }
    }
    if (c != "") {
        if (m == "" || cmp(c, m)) m = c;
    }
    cout << m;
    return 0;
}

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

Thay vì chuyển đổi chuỗi số sang kiểu số, ta giữ nguyên chúng dưới dạng chuỗi và so sánh trực tiếp. Hàm so sánh cmp so sánh độ dài trước (chuỗi nào dài hơn thì lớn hơn), nếu bằng độ dài thì so sánh theo thứ tự từ điển (lexicographical). Cách này an toàn tuyệt đối vì không lo tràn số, xử lý được số có độ dài bất kỳ.

Cách Regex và So sánh chuỗi (Regex & String Sort)

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

int main() {
    string s;
    cin >> s;
    vector<string> nums;
    string cur = "";
    for (char c : s) {
        if (isdigit(c)) cur += c;
        else {
            if (!cur.empty()) {
                nums.push_back(cur);
                cur = "";
            }
        }
    }
    if (!cur.empty()) nums.push_back(cur);

    if (nums.empty()) {
        cout << 0;
        return 0;
    }

    // So sánh thủ công thay vì sort
    string best = nums[0];
    for (string num : nums) {
        if (num.length() > best.length()) best = num;
        else if (num.length() == best.length() && num > best) best = num;
    }
    cout << best;
    return 0;
}

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

Cách tiếp cận này tập trung vào việc tách các số ra thành một danh sách. Duyệt qua xâu, nếu gặp chữ số thì thêm vào chuỗi hiện tại, nếu gặp ký tự khác thì đẩy chuỗi hiện tại vào vector và reset. Cuối cùng, duyệt qua vector để tìm số lớn nhất dựa trên độ dài và thứ tự từ điển. Đây là cách tổng quát hóa của Approach 2, có thể dễ dàng xử lý thêm các yêu cầu phức tạp hơn (ví dụ: loại bỏ số 0 ở đầu).

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

Bài học kinh nghiệm

• Phân tích cấu trúc dữ liệu đầu vào: Xâu chứa xen kẽ số và chữ cái, số được phân tách bởi các ký tự không phải số.
• Phương pháp so sánh số lớn nhất: Số lớn nhất không nhất thiết là số có giá trị lớn nhất về mặt toán học nếu độ dài số quá lớn (vượt quá long long), nhưng trong bài này độ dài xâu chỉ 1000. Tuy nhiên, phương pháp an toàn và phổ biến nhất trong competitive programming khi xử lý 'số lớn' trong xâu là so sánh độ dài trước, sau đó so sánh nếu bằng độ dài.
• Xử lý số 0: Cần chú ý các số như '001' (nếu có) sẽ được xử lý như thế nào. Trong các giải pháp mẫu, '001' được coi là 1 (khi dùng số) hoặc '001' (khi dùng chuỗi). Tuy nhiên, yêu cầu bài toán chỉ tìm 'số lớn nhất', thường ngầm hiểu là giá trị, nên '001' < '1'.

Lỗi thường gặp

• Quên xử lý số nằm ở cuối xâu: Vòng lặp duyệt chỉ xử lý số khi gặp ký tự đặc biệt, nên số cuối cùng cần được kiểm tra sau vòng lặp.
• Tràn số (Overflow): Nếu dùng biến số nguyên (int/long long) để lưu số khi duyệt, số trong xâu có thể dài hơn 18-19 chữ số (vượt quá long long). Giải pháp an toàn là dùng chuỗi để lưu và so sánh.
• Xâu rỗng hoặc không có số: Cần xử lý trường hợp đầu vào không chứa số nào để không in ra kết quả rỗng hoặc lỗi.