Đếm số lượng chuỗi con có giá trị số lớn hơn X trong C++

Cho một chuỗi chỉ chứa các chữ số từ 0-9. Mục tiêu là đếm số lượng chuỗi con (substring) biểu diễn một số thập phân lớn hơn số X cho trước, với điều kiện chuỗi con không được bắt đầu bằng chữ số 0.

Ví dụ minh họa

Ví dụ 1:

• Input: str = "123", X = 12
• Output: 2
• Giải thích: Các chuỗi con > 12 là: "123" (123) và "23" (23). Chuỗi "02", "021", "0" không hợp lệ vì bắt đầu bằng 0.

Ví dụ 2:

• Input: str = "111", X = 100
• Output: 1
• Giải thích: Chỉ có "111" (111) lớn hơn 100.

Thuật toán

1. Duyệt qua từng vị trí i trong chuỗi.
2. Nếu ký tự tại i khác '0', thì tất cả chuỗi con bắt đầu từ i đều hợp lệ.
3. Với mỗi độ dài j từ 1 đến len-i, lấy chuỗi con str.substr(i, j) và chuyển sang số nguyên bằng stoi().
4. Nếu giá trị > X thì tăng bộ đếm.

Mã nguồn C++

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

int greater_X(string str, int x) {
    int count = 0;
    int len = str.length();
    for (int i = 0; i < len; ++i) {
        if (str[i] != '0') {
            for (int j = 1; i + j <= len; ++j) {
                if (stoi(str.substr(i, j)) > x) {
                    count++;
                }
            }
        }
    }
    return count;
}

int main() {
    string str = "987";
    int x = 100;
    cout << "So luong chuoi con lon hon X: " << greater_X(str, x);
    return 0;
}

Kết quả chạy chương trình

So luong chuoi con lon hon X: 1

Độ phức tạp

• Thời gian: O(n²) - n là độ dài chuỗi, do hai vòng lặp lồng nhau.
• Không gian: O(1) - không dùng mảng phụ.

Lưu ý quan trọng

• Hàm stoi() có thể ném ngoại lệ nếu chuỗi con quá lớn (vượt quá INT_MAX). Với chuỗi dài, nên dùng stoll() hoặc so sánh chuỗi trực tiếp.
• Có thể tối ưu bằng cách dừng sớm khi chuỗi con đã chắc chắn > X (so sánh độ dài trước, rồi so sánh từ điển).