Chào các bạn quay lại với LeetCode Daily Challenge ! Hôm nay là ngày thứ 2 trong hành trình của mình với bài toán “Construct K Palindrome Strings”. Ban đầu đọc có thể thấy khó chịu, nhưng khi phân tích kỹ, giải pháp trở nên đơn giản và thú vị hơn. Hãy cùng khám phá! 🚀

👉 Mục tiêu: Mỗi ngày giải 1 bài LeetCode, kiên trì tạo thói quen, từng bước chinh phục các kỹ năng lập trình.

Link : https://leetcode.com/problems/construct-k-palindrome-strings/description/?envType=daily-question&envId=2025-01-11

Mysolution:https://leetcode.com/problems/construct-k-palindrome-strings/solutions/6262490/beat-100-easy-palindrome-construction-explained

    Input: s = "annabelle", k = 2
    Output: true
    Explanation: You can construct two palindromes using all characters in s.
    Some possible constructions: "anna" + "elble", "anbna" + "elle", "anellena" + "b"
  

    Input: s = "leetcode", k = 3
    Output: false
    Explanation: It is impossible to construct 3 palindromes using all the characters of s.
  

    Input: s = "true", k = 4
    Output: true
    Explanation: The only possible solution is to put each character in a separate string.
  

Intuition

Bài toán yêu cầu kiểm tra xem chuỗi s có thể được sắp xếp lại để tạo thành chính xác k chuỗi con là palindrome hay không.

Ngay từ đầu, mình nghĩ đến đặc điểm cốt lõi của palindrome:

• Một chuỗi palindrome chỉ cho phép tối đa một ký tự có tần suất lẻ.
• Nếu số lượng chuỗi con k quá lớn so với độ dài chuỗi s, rõ ràng việc tạo ra k chuỗi palindrome là bất khả thi.

Từ đây, bài toán trở thành việc phân tích tần suất ký tự và tính “lẻ” của chúng.

Approach

1. Kiểm tra nhanh:
   Nếu độ dài chuỗi s nhỏ hơn k, rõ ràng không thể tạo ra k chuỗi con, trả về false.
2. Đếm tần suất ký tự:
   Tạo một mảng cnt[26] để đếm tần suất xuất hiện của từng ký tự trong chuỗi s. Điều này giúp xác định có bao nhiêu ký tự có tần suất lẻ.
3. Đếm số ký tự có tần suất lẻ:
   Một chuỗi palindrome chỉ có thể chứa tối đa một ký tự có tần suất lẻ. Nếu số lượng ký tự có tần suất lẻ (cnt_odd) vượt quá k, việc tạo ra k chuỗi palindrome là không thể. Ngược lại, nếu số lẻ nhỏ hơn hoặc bằng k, chúng ta có thể thực hiện được.
4. Kết quả:
   Trả về true nếu cnt_odd <= k, ngược lại trả về false.

Complexity

• Độ phức tạp thời gian:
  O(n)O(n), với nn là độ dài chuỗi s.
  • Đếm tần suất ký tự cần O(n)O(n).
  • Duyệt qua mảng cnt (26 ký tự) cần O(26)=O(1)O(26) = O(1).
• Độ phức tạp không gian:
  O(1)O(1).
  • Chỉ sử dụng một mảng cố định cnt có kích thước 26 để lưu tần suất ký tự.

Code

class Solution {
public:
    bool canConstruct(string s, int k) {
        // Nếu chuỗi quá ngắn để tạo ra k chuỗi con, trả về false
        if (s.length() < k) {
            return false;
        }

        int cnt[26] = {0}; // Mảng tần suất cho các ký tự từ 'a' đến 'z'

        // Đếm tần suất xuất hiện của từng ký tự trong chuỗi
        for (char c : s) {
            cnt[c - 'a']++;
        }

        int cnt_odd = 0; // Số lượng ký tự có tần suất lẻ

        // Đếm số ký tự có tần suất lẻ
        for (int i = 0; i < 26; i++) {
            if (cnt[i] % 2 == 1) {
                cnt_odd++;
            }
        }

        // Nếu số ký tự lẻ nhiều hơn k, không thể tạo được k chuỗi palindrome
        return cnt_odd <= k;
    }
};

Testcase

int main() {
    Solution solution;

    // Test case 1: Kết quả mong đợi: true
    string s1 = "annabelle";
    int k1 = 2;
    cout << "Test Case 1: " << (solution.canConstruct(s1, k1) ? "true" : "false") << endl;

    // Test case 2: Kết quả mong đợi: false
    string s2 = "abc";
    int k2 = 4;
    cout << "Test Case 2: " << (solution.canConstruct(s2, k2) ? "true" : "false") << endl;

    // Test case 3: Kết quả mong đợi: true
    string s3 = "aabbcc";
    int k3 = 3;
    cout << "Test Case 3: " << (solution.canConstruct(s3, k3) ? "true" : "false") << endl;

    return 0;
}

Cảm nhận

Bài này đọc có vẻ lằng nhằng nhưng cuối cùng lại khá đơn giản trong lúc cài thuật toán chỉ cần hiểu rõ tính chất của palindrome . Vậy là xong Day 2 !!! . Cảm ơn mọi người đã dành thời gian cho bài post vui vui về thuật toán này .Mình mong nó giúp ích nào được cho các bạn 😊