LeetCode 1400 - Construct K Palindrome Strings

LeetCode Problem 1400

Difficulty: 🟡 Medium
Topics: Hash Table, String, Greedy, Counting

Solution

Problem Understanding

The problem is asking whether a given string s can be rearranged to form exactly k non-empty palindrome strings using all characters in s. In other words, we need to partition s into k palindromes such that each character of s is used exactly once.

A palindrome is a string that reads the same forward and backward. For a string to be a palindrome, at most one character can have an odd frequency; all other characters must appear an even number of times to mirror around the center.

The input consists of a string s of lowercase English letters with a length up to 100,000, and an integer k (up to 100,000). The output is a boolean: true if the string can be rearranged into k palindromes, and false otherwise.

Important edge cases to note are when k is larger than the length of s (impossible to make more palindromes than characters), or when all characters are unique and k is small (palindromes of length >1 are required, which may not be possible).

Approaches

A brute-force approach would attempt to generate all possible partitions of s into k substrings, and then check if each substring is a palindrome. While this guarantees correctness, the time complexity is exponential and completely impractical for the given constraints (string length up to 10^5).

The key insight for an optimal solution comes from character frequencies. For each palindrome, we can have at most one character with an odd count (as the middle character). Therefore, the minimum number of palindromes needed is equal to the number of characters in s that have an odd count. If this number is greater than k, it is impossible to construct k palindromes. Additionally, we cannot create more palindromes than the total number of characters (k > len(s)), because each palindrome must be non-empty.

This leads to an efficient approach: count the frequency of each character, determine how many characters have odd counts, and check the two conditions: odd_count <= k <= len(s).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k^n)	O(n)	Generate all partitions and check palindromes, infeasible for large n
Optimal	O(n)	O(1)	Count character frequencies, compute odd-count characters, check conditions

Algorithm Walkthrough

1. Initialize a frequency array or hash map to count occurrences of each character in s.
2. Iterate over the string s and populate the frequency counts.
3. Initialize a counter odd_count to zero.
4. Iterate over the frequency counts. For each character with an odd frequency, increment odd_count.
5. Check if odd_count is less than or equal to k (each palindrome can accommodate at most one odd character).
6. Also check if k is less than or equal to the length of s (cannot have more palindromes than characters).
7. Return true if both conditions are satisfied, otherwise return false.

Why it works: Each palindrome can have at most one character with an odd frequency at its center. Therefore, the minimum number of palindromes needed is exactly the number of characters with odd frequencies. If k is less than this number, it is impossible. The other constraint (k <= len(s)) ensures each palindrome is non-empty. This guarantees correctness.

Python Solution

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k > len(s):
            return False
        
        freq = [0] * 26
        for char in s:
            freq[ord(char) - ord('a')] += 1
        
        odd_count = sum(1 for count in freq if count % 2 == 1)
        return odd_count <= k

The Python implementation first checks the trivial case where k is larger than the string length. Then, it uses a fixed-size array for character counts to optimize space and performance. The sum of odd frequencies determines the minimum number of palindromes needed. The final boolean expression directly checks the feasibility condition.

Go Solution

func canConstruct(s string, k int) bool {
    if k > len(s) {
        return false
    }

    freq := [26]int{}
    for _, c := range s {
        freq[c-'a']++
    }

    oddCount := 0
    for _, count := range freq {
        if count%2 == 1 {
            oddCount++
        }
    }

    return oddCount <= k
}

The Go implementation mirrors the Python logic. A fixed-size array of 26 integers is used for frequency counts. Iteration over the string and the array calculates oddCount. The final condition checks feasibility. Go handles string iteration as runes, but since input is lowercase English letters, subtracting 'a' gives the correct index.

Worked Examples

Example 1: s = "annabelle", k = 2

Frequency counts: a:2, n:2, b:1, e:3, l:2

Odd counts: b(1), e(3) → total odd_count = 2

Check: 2 <= 2 and 2 <= 9 → True

Example 2: s = "leetcode", k = 3

Frequency counts: l:1, e:3, t:1, c:1, o:1, d:1

Odd counts: l,e,t,c,o,d → odd_count = 6

Check: 6 <= 3? No → False

Example 3: s = "true", k = 4

Frequency counts: t:1, r:1, u:1, e:1

Odd counts = 4

Check: 4 <= 4 and 4 <= 4 → True

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass over string to count characters, n = len(s)
Space	O(1)	Fixed-size array of 26 letters independent of input size

The time complexity is linear in the length of the string. Space complexity is constant since the frequency array does not scale with input size.

Test Cases

# Provided examples
assert Solution().canConstruct("annabelle", 2) == True  # multiple palindromes possible
assert Solution().canConstruct("leetcode", 3) == False  # too few characters for palindromes
assert Solution().canConstruct("true", 4) == True  # one character per palindrome

# Edge cases
assert Solution().canConstruct("a", 1) == True  # single character, single palindrome
assert Solution().canConstruct("a", 2) == False  # cannot have more palindromes than characters
assert Solution().canConstruct("aaabbb", 2) == True  # two palindromes, odd counts balanced
assert Solution().canConstruct("aaabbb", 1) == False  # cannot make a single palindrome with two odd characters
assert Solution().canConstruct("abc", 3) == True  # each character as its own palindrome
assert Solution().canConstruct("abc", 2) == False  # not enough palindromes to accommodate odd counts

Test	Why
"annabelle", 2	Typical case with multiple palindromes
"leetcode", 3	Impossible due to odd count constraint
"true", 4	Each character can form a palindrome
"a", 1	Minimal input
"a", 2	k > length, invalid
"aaabbb", 2	Odd counts can be distributed among palindromes
"aaabbb", 1	Odd counts exceed k
"abc", 3	Each unique character forms its own palindrome
"abc", 2	Not enough palindromes for odd counts

Edge Cases

One important edge case is when k exceeds the length of the string. This is impossible because each palindrome must contain at least one character, and the implementation explicitly checks for this.

Another edge case is when all characters have odd frequency. The minimum number of palindromes required equals the number of odd characters. The solution handles this by counting the odd frequencies and comparing them with k.

A third edge case is when k equals the string length. Here, each character must become its own palindrome. The algorithm correctly allows this scenario because the number of odd characters cannot exceed k, and the check k <= len(s) ensures feasibility.