\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hướng dẫn}}\)

• \(Mục tiêu:\)

A) Chọn vị trí đặt chữ

😎 Chọn chữ để đặt

C) Tính kết quả

D) Chọn kết quả tối ưu nhất

\(\color{goldenrod}{\text{Tiếp cận}}\)

• Chọn vị trí đặt chữ và chọn chữ để đặt

Duyệt toàn tập: Thử từng vị trí và thử từng chữ để đặt, có \(n + 1\) vị trí và \(26\) kí tự nên có tất cả \(O(26^n)\) cách

Duyệt trâu: Thử từng vị trí và thử từng chữ để đặt, có \(n + 1\) vị trí và ta chỉ cần đặt chữ \(c\) và chữ \(u\) (những chữ khác không ảnh hưởng kết quả) nên có tất cả \(O(2^n)\) cách:

Duyệt tối ưu: Thử đặt chữ \(c\) ở đầu xâu để ghép với tất cả \(u\) ở sau hoặc thử đặt chữ \(u\) ở cuối để ghép với tất cả chữ \(c\) ở trước. Có tất cả \(O(2)\) cách

• Tính kết quả và chọn kết quả tối ưu nhất

Thử từng xâu con và đếm xem có bao nhiêu xâu "\(cu\)". Nên có tất cả \(O(2^n)\) xâu

Thử từng xâu con độ dài 2 và đếm xem có bao nhiêu xâu "\(cu\)". Nên có tất cả \(O(n^2)\) xâu

Duyệt từng kí tự từ trái qua phải, nếu kí tự hiện tại là \(u\) thì cộng vào kết quả số lượng kí tự \(c\) bên trái nó băng quy hoạch động. Nên chỉ mất \(O(n)\)

Kết quả tối ưu nhất là max của các cách để đặt thêm một kí tự vào xâu

\(\color{green}{\text{Code tham khảo }}\): Approach

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n)\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>

using namespace std;

long long solve(const string &s)
{
    int cnt_c = 0;
    long long res = 0;
    for (char c : s)
    {
        if (c == 'c')
        {
            ++cnt_c;
        }

        if (c == 'u')
        {
            res += cnt_c;
        }
    }

    return res;
}

int main()
{
    int n;
    cin >> n;

    string s;
    cin >> s;

    cout << max(solve(s + 'u'), solve('c' + s));
    return 0;
}