We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Construct K Palindrome Strings

Difficulty: Medium

Problem Description

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

Key Insights

  • A palindrome reads the same forwards and backwards.
  • For a string to be a palindrome, at most one character can have an odd frequency (for strings of odd length).
  • To construct k palindromes, we need to assess the number of characters with odd frequencies in the string.
  • The minimum number of palindromes we can form is determined by the number of characters with odd counts, as each odd character requires its own palindrome.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s, as we need to count the frequency of characters. Space Complexity: O(1), since the frequency array will have a fixed size of 26 for lowercase English letters.

Solution

To determine if we can construct k palindromes from the string, we can follow these steps:

  1. Count the frequency of each character in the string using a hash table (or array).
  2. Count how many characters have an odd frequency.
  3. If the number of odd frequency characters is less than or equal to k, return true; otherwise, return false.

The algorithm primarily uses counting (hash table) and checks the conditions necessary for forming palindromes.

Code Solutions

def canConstruct(s: str, k: int) -> bool:
    from collections import Counter
    
    # Count frequency of each character
    freq = Counter(s)
    odd_count = sum(1 for count in freq.values() if count % 2 != 0)
    
    # Check if we can form k palindromes
    return odd_count <= k
← Back to All Questions