Bài toán đếm các từ có thể tách được từ 1 chuỗi str

[AzDev (Az)]

“Cho một chuỗi kí tự str và một từ word . Ta có thể tách các kí tự trong str ra để tạo thành một từ. Hãy tính xem số lượng từ word riêng biệt được tạo nhiều nhất từ những kí tự trong str là bao nhiêu. Ví dụ: Với str = “loonbalxballpoon”, word = “balloon”, đầu ra là 2.”

Ý tưởng của em: Cho 1 vòng For chạy từ 0 tới str.length() - 1, tìm các substring có độ dài >2 (mỗi một kí tự chỉ lấy substring, không lấy 2 substring có chứa cùng một str[i]) thuộc str, sau đó ghép.

Em làm như ý tưởng trên thì hơn nửa test bị TLE (giới hạn 1<= str.size(), word.size() <=10^5 )
Ai có ý tưởng gì không giúp em với ạ!
Em cảm ơn ạ!

[noname00 (HK boy)]

Tách các kí tự theo hướng nào nhỉ? Nếu chỉ là “tách” thuần tuý thì test ví dụ có nhiều hơn 2 đáp số đấy.

s = loonbalxballpoon
=>      bal    l oon
=>      ba    ll oon
=>      b    all oon
=>          ball oon

[AzDev (Az)]

Mỗi kí tự chỉ được dùng 1 lần thôi anh ạ!

[noname00 (HK boy)]

Vậy thì bài này chỉ là đếm kí tự đơn giản thôi. Cần bao nhiêu kí tự để tạo thành 1 word, có bao nhiêu kí tự -> số từ đếm được.