Construct K Palindrome Strings - Leetcode Solution

Problem Statement:

You are given a string s and an integer k. You can construct k non-empty palindromic substrings using all the characters in s.

Return True if you can use all the characters in s to construct k palindrome strings or False otherwise.

Example:

Input: s = "annabelle", k = 2 Output: true Explanation: You can construct two palindromes using all characters in s as follows:

• "anna" and "elle"
• or "ana" and "nelle"

Solution:

Approach:

To construct k palindromic substrings, we need to divide the string into k substrings such that we can make each substring a palindrome using all the characters in that substring.

1. If the length of the string s is less than k, then we cannot construct k palindrome substrings. Therefore, return False.
2. If the length of the string s is equal to k, then each character of the string can be considered as a palindrome substring. Therefore, return True.
3. If the characters in the string cannot be distributed into k substrings, then we cannot construct k palindrome substrings. Therefore, return False.
4. If s can be divided into k substrings then check whether we can make each substring a palindrome using all the characters in that substring. For this, we can use a dictionary to count the frequency of each character in the string s. Then, we can iterate over the dictionary and check whether we can form k palindromic substrings using the characters with even counts and one palindromic substring using the character with an odd count. If we can form k palindromic substrings using all the characters in s, then we return True. Otherwise, return False.

Python Code:

class Solution: def canConstruct(self, s: str, k: int) -> bool:

    # Condition 1
    if len(s) < k:
        return False
    
    # Condition 2
    if len(s) == k:
        return True
    
    # Count frequency of characters in s
    char_freq = {}
    for char in s:
        if char in char_freq:
            char_freq[char] += 1
        else:
            char_freq[char] = 1
    
    # Count the number of characters with odd counts
    odd_count = 0
    for count in char_freq.values():
        if count % 2 == 1:
            odd_count += 1
    
    # Condition 3 - cannot distribute characters into k palindromic substrings
    if odd_count > k:
        return False
    
    # Condition 4 - check whether we can form k palindromic substrings
    palindromes = 0
    for count in char_freq.values():
        if count % 2 == 0:
            palindromes += count // 2
        else:
            palindromes += (count - 1) // 2
    
    if palindromes >= k:
        return True
    else:
        return False

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the string s. We iterate over the string s multiple times and create a dictionary of character frequencies, which takes O(n) time. The other operations are constant time.

1