Today’s problem

https://leetcode.com/problems/construct-k-palindrome-strings/description/

Intuition

A palindrome can have at most one character with an odd count. Therefore, to create $k$ palindrome strings, there must be at most $k$ characters in string $s$ with an odd count.

Additionally, since there are at most 26 different characters, if $26 \leq k$, the result must be true. However, if the length of $s$ is less than $k$, it would be false.

To prove this, let the number of characters with odd counts be $cntO$, and let the count of all remaining characters be $2 \times cntE$.

If all character counts are even, we can always create palindrome strings as long as $k \leq N$, where $N$ is the total length of $s$. This is because we can place one character on the leftmost side of a palindrome string and its duplicate on the rightmost side, preserving the palindrome structure.

Since $k \leq N$, it follows that $k \leq cntO + 2 \times cntE$. Thus, $k - cntO \leq 2 \times cntE$. This implies that all characters with odd counts can be used to form $cntO$ palindrome strings.

Now, we have already proved that if all character counts are even, we can always create palindrome strings as long as $k \leq N$, where $N$ is the total length of $s$. So in this case, if $cntO \le k$, the result would be ture, otherwise, it would be false.

Finally, the question reduces to the proposition that $k \leq N$ when all characters have even counts, which is always true.

Trick

Since there are at most 26 different characters, if $26 \leq k$, the result must be true.

Approach

Now we only need to calculate the occurence of every character and test whether the odd-count characters are less or equal to $k$ or not.

Complexity

  • Time complexity: $O(N)$, while N is the length of the string.

  • Space complexity: $O(1)$, while the count of 26 characters are stored.

Code

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        cnt = [0] * 26
        if len(s) < k:
            return False
        if k > 25:
            return True
        # The code that makes the code run very fast.
        for ch in s:
            cnt[ord(ch) - ord('a')] += 1
        x = 0
        for i in range(26):
            if cnt[i] % 2 == 1:
                x += 1
        return x <= k

image.png