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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Construct K Palindrome Strings

Number: 1502

Difficulty: Medium

Paid? No

Companies: Microsoft, Bloomberg, Google, Uber

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

  • Count the frequency of each character in the string.
  • A palindrome can have at most one character with an odd frequency.
  • Each palindrome string can incorporate one odd frequency character.
  • The minimum number of palindromes required equals the number of odd frequency characters.
  • Additionally, k must not exceed the length of s since each palindrome should be non-empty.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s. Space Complexity: O(1), since we only count characters from a fixed alphabet (26 lowercase letters).

Solution

The approach is to first count the frequency of each character in the string using a hash table (or dictionary). Then, we determine the number of characters that appear an odd number of times, as each palindrome can accommodate one odd count character. If the number of odd frequency characters is less than or equal to k and k is also less than or equal to the length of s, then it is possible to rearrange s into k palindrome strings. Otherwise, it is not possible.

Code Solutions

def canConstruct(s: str, k: int) -> bool:
    # If k is more than the length of s, it is impossible to create k non-empty strings.
    if k > len(s):
        return False
    
    # Count frequency of each character in s.
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    
    # Count the number of characters that have an odd frequency.
    odd_count = sum(1 for count in char_count.values() if count % 2 != 0)
    
    # Check if odd_count is less than or equal to k.
    return odd_count <= k

# Example usage:
print(canConstruct("annabelle", 2))  # Output: True
← Back to All Questions