\(\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{Hint 1 <Brute-forces>}}\)

• Thử xóa từng kí tự

Với mỗi trường hợp ta thử xóa từng kí tự và sau đó sắp xếp nó lại để tìm ra xâu nhỏ nhất thỏa mãn

\(\color{orange}{\text{Hint 2 <Implementation>}}\)

• Sau khi xóa, kí tự ở vị trí xóa sẽ đầu tiên thay thế bởi kí tự đứng sau (nếu có). Sau đó các kí tự khác sẽ dồn lên trên

Mình cần tìm xâu nhỏ nhất, nên sau khi mình xóa một kí tự \(s_i\) thì phần tử sau nó \(s_{i + 1}\) nên bé hơn phần tử đứng trước để nó trở thành xâu nhỏ hơn với độ dài \(|S| - 1\)

Ví dụ: "aabac" \(\Rightarrow\) "aaac" (bé nhất trong các xâu "abac", "aaac", "aaba")

Nhưng trong tất cả các vị trí thỏa mãn \(s_i > s_{i + 1}\) thì vị trí nhỏ nhất mình chọn sẽ giúp mình có được xâu nhỏ nhất.

\(\color{green}{\text{Preference AC Code }}\): Implementation

\(^{^{\color{purple}{\text{Complexity : }} O(n)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

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

    string s;
    cin >> s;

    int p = n - 1; /// Neu khong tim duoc vi tri thoa man thi minh se xoa phan tu cuoi cung
    for (int i = 0; i + 1 < n; ++i)
        if (s[i] > s[i + 1])  /// Neu tim duoc vi tri thoa man
            { p = i; break; } /// thi minh gan no bang gia tri do va khong can duyet tiep nua

    for (int i = 0; i < n; ++i)
        if (i != p)       /// xoa phan tu do chi don gian la minh khong in no ra
            cout << s[i]; /// xuat phan tu do ra neu khong phai vi tri can xoa

    return 0;
}

\(\color{orange}{\text{Hint 3 <Space-Optimization>}}\)

• Ta có thể không cần lưu xâu \(S\)

\(\color{green}{\text{Preference AC Code }}\): Online Solving

\(^{^{\color{purple}{\text{Complexity : }} O(n)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

inline bool isLowerLatin(char c) { return 'a' <= c && c <= 'z'; } /// Neu no la ki tu thuong
int main()
{
    int n;
    cin >> n; /// so phan tu

    char pre; /// ki tu truoc
    while (pre = getchar(), pre != EOF && !isLowerLatin(pre)); /// loai bo ki tu thua cho toi khi gap chu cai thuong

    bool ok = false; // danh dau da xoa phan tu (true) hay chua xoa (false)
    for (int i = 1; i <= n; ++i) /// duyet qua tung phan tu
    {
        char cur = getchar(); /// nhan phan tu hien tai
        if (!ok && (i == n || pre > cur)) /// neu chua danh dau, va phan tu o vi tri cuoi hoac phan tu truoc lon hon
            ok = true; /// danh dau no va bo qua
        else
            cout << pre; /// xuat phan tu do

        pre = cur;
    }


    return 0;
}