Hiểu bài toán

Bài toán yêu cầu tìm số bước tối thiểu để biến một xâu ký tự S gồm các ký tự '.', '#' và 'o' thành một xâu 'good'. Xâu 'good' được định nghĩa là xâu không chứa ký tự '#'. Trong mỗi bước, ta có thể thực hiện một trong hai thao tác:

1. Xóa một ký tự '.' ở bất kỳ đâu.
2. Di chuyển một ký tự 'o' sang trái hoặc sang phải. Khi di chuyển, ký tự 'o' sẽ vượt qua các ký tự khác và chỉ dừng lại khi gặp một ký tự '#' hoặc '.' hoặc biên của xâu. Việc di chuyển qua một '#' là không được phép.

Mục tiêu là tìm cách loại bỏ tất cả '#' và '.' (hoặc di chuyển 'o' vào vị trí của chúng) sao cho số bước thực hiện là nhỏ nhất. Nhìn chung, ta cần loại bỏ các ký tự '#' và có thể cần loại bỏ thêm một số '.' để tạo đường đi cho 'o'.

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

Cách Duyệt qua tất cả các cách chia cắt (Split Point)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    // Giả lập file I/O
    // freopen("pchar.inp", "r", stdin);
    // freopen("pchar.out", "w", stdout);

    int n;
    string s;
    cin >> n >> s;

    // Tính toán số lượng '.' ở bên phải từng vị trí (suffix)
    vector<int> dot_suffix(n + 2, 0);
    for (int i = n - 1; i >= 0; --i) {
        dot_suffix[i] = dot_suffix[i + 1] + (s[i] == '.' ? 1 : 0);
    }

    // Chi phí cơ bản là xóa tất cả các ký tự '.'
    int result = dot_suffix[0];
    int hash_left = 0; // Số lượng '#' ở bên trái vị trí hiện tại

    // Duyệt qua từng vị trí k (điểm chia cắt)
    // Giả sử chúng ta giữ lại các ký tự '#' nằm ở bên trái hoặc bằng k,
    // và xóa các ký tự '.' nằm ở bên trái hoặc bằng k.
    // Các ký tự '#' ở bên phải k phải được xóa (chi phí 0, vì '#' không được phép trong xâu cuối).
    // Các ký tự '.' ở bên phải k phải được xóa để tạo đường đi (chi phí 1).
    for (int i = 0; i < n; ++i) {
        if (s[i] == '#') {
            hash_left++;
        }
        // Chi phí tại điểm chia cắt i:
        // hash_left: số lượng '#' bên trái (phải xóa nếu muốn xóa hết '#' hoặc dùng làm chi phí)
        // dot_suffix[i + 1]: số lượng '.' bên phải (phải xóa)
        result = min(result, hash_left + dot_suffix[i + 1]);
    }

    cout << result << endl;
    return 0;
}

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

Hầu hết các solution đều sử dụng phương pháp này. Logic như sau: Để có xâu 'good' (chỉ chứa 'o'), ta cần xử lý các ký tự '#' và '.'.

• Các ký tự '#' ở bên phải điểm chia cắt $k$ (ví dụ $k$ là vị trí cuối cùng của ký tự '#' được giữ lại) đều được coi là đã được xử lý (xóa) với chi phí 0 (vì chỉ cần xóa '#' là được, không có chi phí di chuyển).
• Các ký tự '.' ở bên phải $k$ cũng cần được xóa để các 'o' có thể đi qua.
• Các ký tự '#' ở bên trái $k$ có thể được giữ lại hoặc xóa. Tuy nhiên, xét trong bài toán này, việc giữ '#' chỉ có ý nghĩa nếu ta muốn giữ nguyên trật tự. Nhưng do ta cần xóa hết '#' để xâu thành 'good', hoặc chí ít '#' không được xuất hiện. Tuy nhiên, các solution tìm giá trị nhỏ nhất của hash_left + dot_suffix[i+1].
  • hash_left: Số lượng '#' từ đầu đến $i$. Nếu ta chọn $i$ là điểm chia cắt, và các '#' này nằm trước các ký tự 'o' cần giữ, ta có thể phải xóa chúng.
  • dot_suffix[i+1]: Số lượng '.' sau $i$. Các '.' này chắn đường đi của 'o' nên phải xóa.
  • Công thức min(result, hash_left + dot_suffix[i+1]) tìm ra vị trí chia cắt tối ưu sao cho tổng số '#' bên trái và '.' bên phải là nhỏ nhất. Đây chính là chi phí xóa các ký tự cản trở này.

Cách Tối ưu hóa Space O(1)

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

int main() {
    // freopen("pchar.inp", "r", stdin);
    // freopen("pchar.out", "w", stdout);

    int n;
    string s;
    cin >> n >> s;

    int total_dots = 0;
    for (char c : s) {
        if (c == '.') total_dots++;
    }

    int current_hash = 0;
    int current_dots = total_dots;
    int ans = total_dots; // Chi phí nếu xóa hết '.'

    for (int i = 0; i < n; ++i) {
        if (s[i] == '#') {
            current_hash++;
        } else if (s[i] == '.') {
            current_dots--;
        }
        // Tại mỗi bước, tính chi phí:
        // Xóa các '#' ở bên trái (current_hash)
        // Xóa các '.' ở bên phải (current_dots)
        ans = min(ans, current_hash + current_dots);
    }

    cout << ans;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1) (không tính không gian lưu xâu)

Phương pháp này là biến thể của phương pháp trên nhưng không cần mảng phụ để lưu suffix sum.

• Ta duyệt một lần để đếm tổng số '.' (total_dots).
• Trong một vòng lặp duy nhất từ trái sang phải:
  • current_hash tăng lên khi gặp '#'.
  • current_dots giảm đi khi gặp '.' (vì '.' này đã nằm ở bên trái, không còn nằm ở bên phải).
  • Tại mỗi vị trí, ta cập nhật ans = min(ans, current_hash + current_dots). Biến này thể hiện chi phí xóa '#' bên trái và '.' bên phải tại thời điểm đó.

Cách Quy hoạch động/Thay đổi trực tiếp chuỗi

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

int main() {
    // freopen("PCHAR.inp", "r", stdin);
    // freopen("PCHAR.out", "w", stdout);

    int n; cin >> n;
    string s; cin >> s;

    // a[i] là số lượng '#' từ đầu đến i-1
    vector<int> a(n + 1);
    a[0] = 0;
    for (int i = 0; i < n; ++i) {
        a[i + 1] = a[i] + (s[i] == '#');
    }

    // Phép toán: n - i - (a[n] - a[i])
    // n - i: độ dài đoạn từ i đến n-1
    // (a[n] - a[i]): số lượng '#' trong đoạn đó
    // => Số lượng '.' trong đoạn đó

    int ans = min(a[n], n - a[n]); // Xóa hết '#' hoặc xóa hết '.'
    for (int i = 1; i <= n; ++i) {
        // Tại điểm chia i:
        // Chi phí = (Số # bên trái) + (Số . bên phải)
        // Số # bên trái = a[i]
        // Số . bên phải = (Tổng ký tự bên phải) - (Số # bên phải)
        //                = (n - i) - (a[n] - a[i])
        ans = min(ans, a[i] + (n - i) - (a[n] - a[i]));
    }
    cout << ans;

    return 0;
}

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

Đây là cách diễn giải khác của cùng một logic.

• a[i] là mảng prefix sum của số lượng '#'.
• Để tính số lượng '.' ở bên phải vị trí i, ta lấy tổng độ dài phần còn lại (n - i) trừ đi số lượng '#' trong phần đó (a[n] - a[i]).
• Công thức ans = min(ans, a[i] + (n - i) - (a[n] - a[i])) chính là Số # bên trái + Số . bên phải.
• Solution này cũng đề cập đến việc so sánh với min(a[n], n - a[n]), tức là các trường hợp đặc biệt: xóa hết '#' (chi phí = số #) hoặc xóa hết '.' (chi phí = số .).

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

Bài học kinh nghiệm

• Bài toán có thể biến đổi thành tìm điểm chia cắt sao cho tổng số '#' ở bên trái và '.' ở bên phải là nhỏ nhất.
• Ký tự 'o' không ảnh hưởng đến chi phí tính toán trực tiếp, mà chỉ là các ký tự còn lại sau khi xử lý '#' và '.'.
• Chi phí xóa '#' là 1 (nhưng trong các solution có vẻ như coi việc loại bỏ '#' là bắt buộc và chỉ đếm số lượng, hoặc chi phí xử lý '#' nằm trong logic tổng quát). Thực tế, các solution tập trung vào việc loại bỏ '.' để tạo đường đi và loại bỏ '#' để có xâu 'good'.

Lỗi thường gặp

• Lầm tưởng rằng cần phải di chuyển 'o', trong khi chỉ cần xóa các chướng ngại vật ('.' và '#') là đủ.
• Sai lệch trong việc tính toán vị trí của các ký tự dẫn đến công thức sai (ví dụ nhầm lẫn giữa left và right).