Construct K Palindrome Strings

Leetcode Problem:

• Construct K Palindrome Strings

Summary

• Given a string s and an integer k, return true if all characters in s can be used to construct non-empty k palindrome strings or false otherwise.

Approach

• This solution uses a frequency count array to store the frequency of each character in the string
• It then checks the number of characters with odd frequencies, which are the characters that can only appear in one palindrome
• If the number of such characters is less than or equal to k, it means that all characters can be used to construct k palindrome strings.

Complexity

• O(n) where n is the length of the string, because we are iterating over the string twice (to count frequencies and to check odd frequencies).

Explanation

• We start by checking if the length of the string is less than k
• If it is, we return false because we cannot construct k palindrome strings
• We then create a frequency count array cnt of size 128 to store the frequency of each character in the string
• We iterate over the string and increment the count of each character in the array
• We then iterate over the characters 'a' to 'z' and count the number of characters with odd frequencies
• If this number is less than or equal to k, we return true because we can construct k palindrome strings
• Otherwise, we return false.

Solution Code:

class Solution {
public:
    bool canConstruct(string s, int k) {
        if(s.size() < k) return false;
        int cnt[128];
        for(char c: s){
            cnt[c]++;
        }
        int odd = 0;
        for(int i = 'a'; i <= 'z'; i++){
            odd += cnt[i] & 1;
        }
        return odd <= k;
    }
};