Chào mừng anh em quay trở lại với series LeetCode Daily Challenge! Lại là mình loser1 đây !!! Sau Ba ngày đầu tiên với những bài toán về xâu và stack, hôm nay chúng ta sẽ tiếp tục với một bài toán thú vị về xử lý xâu. Let’s crack it! 💪

Input: s = "abaacbcbb"
Output: 5
Explanation: 
We do the following operations:
- Choose index 2, then remove the characters at indices 0 and 3. The resulting string is s = "bacbcbb".
- Choose index 3, then remove the characters at indices 0 and 5. The resulting string is s = "acbcb".

Input: s = "aa"
Output: 2
Explanation: We cannot perform any operations, so we return the length of the original string.

Intuition

Khi đọc đề bài này, điều đầu tiên mình nghĩ đến là làm sao để tối ưu việc xóa các ký tự. Mấu chốt nằm ở chỗ chúng ta cần tìm ra pattern của các ký tự giống nhau và xóa chúng một cách thông minh! 🤔

Approach

Mình xin phân tích chi tiết cách tiếp cận bài toán này:

1. Phân Tích Yêu Cầu Đề Bài

• Ở mỗi bước, ta được chọn một vị trí i bất kỳ
• Điều kiện để chọn i:
• Phải có ít nhất 1 ký tự giống s[i] ở bên trái
• Phải có ít nhất 1 ký tự giống s[i] ở bên phải
• Sau khi chọn i, ta sẽ:
• Xóa ký tự giống s[i] gần nhất bên trái
• Xóa ký tự giống s[i] gần nhất bên phải

2. Phân Tích Test Cases

Test Case 1: "abaacbcbb"
Bước 1: Chọn i = 2 ('a')
- Trước: "abaacbcbb"
- Xóa 'a' ở index 0 và 3
- Sau: "bacbcbb"

Bước 2: Chọn i = 3 ('b')
- Trước: "bacbcbb"
- Xóa 'b' ở index 0 và 5
- Sau: "acbcb"
-> Kết quả: 5

Test Case 2: "aa"
- Không thể thực hiện thao tác nào
-> Kết quả: 2

3. Chiến Lược Tối Ưu

1. Quan sát quan trọng:

• Một ký tự chỉ có thể bị xóa nếu nó có ít nhất 3 ký tự giống nhau trong xâu
• Ký tự ở giữa sẽ được dùng làm pivot để xóa 2 ký tự còn lại

1. Cách tiếp cận tham lam (Greedy):

• Đếm tần suất của mỗi ký tự
• Nếu một ký tự xuất hiện ít nhất 3 lần, ta có thể xóa 2 trong số đó
• Lặp lại quá trình cho đến khi không thể xóa thêm

1. Chi tiết thực hiện:

Ví dụ với "abaacbcbb":
- Đếm tần suất ban đầu:
  'a': 3 lần -> có thể xóa 2 lần -> còn 1 'a'
  'b': 4 lần -> có thể xóa 2 lần -> còn 2 'b'
  'c': 2 lần -> không thể xóa
-> Xâu cuối cùng có độ dài 5

4. Các trường hợp đặc biệt:

• Xâu có độ dài 1 hoặc 2: không thể xóa
• Xâu chỉ có 2 ký tự giống nhau: không thể xóa
• Xâu có nhiều nhóm ký tự giống nhau: xử lý từng nhóm độc lập

Complexity

• Time complexity: $$O(n)$$ – chỉ cần duyệt qua xâu một lần
• Space complexity: $$O(1)$$ – chỉ cần một mảng đếm tần suất 26 ký tự

Code

class Solution {
public:
    int minimumLength(string s) {
        // Sử dụng map để đếm tần suất
        unordered_map<char, int> cnt; 

        // Bước 1: Đếm tần suất xuất hiện của mỗi ký tự
        for (char c : s) {
            cnt[c] += 1; 
        }

        int ans = 0; 
        // Bước 2: Tính toán độ dài palindrome tối thiểu
        for (auto it : cnt) {
            // Nếu ký tự xuất hiện chẵn lần -> đóng góp 2
            if (it.second % 2 == 0) {
                ans += 2; 
            } 
            // Nếu ký tự xuất hiện lẻ lần -> đóng góp 1 (đặt ở giữa)
            else {
                ans += 1; 
            }
        }
        return ans;
    }
};

Chương Trình Test

int main() {
    Solution sol;

    // Test case 1: Xâu đơn giản
    cout << "Test 1: " << sol.minimumLength("aabbaa") << endl;
    // Expected: 4 (abba)

    // Test case 2: Một ký tự
    cout << "Test 2: " << sol.minimumLength("a") << endl;
    // Expected: 1

    // Test case 3: Nhiều ký tự lẻ
    cout << "Test 3: " << sol.minimumLength("abcabc") << endl;
    // Expected: 5 (abcba)

    return 0;
}

Tips & Tricks Quan Trọng

1. Khi xử lý bài toán string, luôn xét các case đặc biệt trước
2. Với bài toán tối ưu, thường có thể áp dụng tư duy tham lam
3. Vẽ sơ đồ hoặc mô phỏng thao tác trên giấy sẽ giúp hiểu bài tốt hơn

Pro tip: Khi làm bài kiểu này, anh em nên:

• Vẽ ra giấy để theo dõi các bước xóa
• Thử nhiều test case khác nhau
• Tìm quy luật chung trước khi code

Lại Code editor cho ae ……..