1400. Construct K Palindrome Strings Solution

The problem

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

Example 1:

Input: s = "annabelle", k = 2
Output: true
Explanation: You can construct two palindromes using all characters in s.
Some possible constructions "anna" + "elble", "anbna" + "elle", "anellena" + "b"

Example 2:

Input: s = "leetcode", k = 3
Output: false
Explanation: It is impossible to construct 3 palindromes using all the characters of s.

Example 3:

Input: s = "true", k = 4
Output: true
Explanation: The only possible solution is to put each character in a separate string.

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.
1 <= k <= 10⁵

Approach overview

Problem Overview: You are given a string s and an integer k. The task is to determine whether you can rearrange all characters of the string to form exactly k palindrome strings. Each character must be used exactly once.

Approach 1: Character Frequency Counting (Greedy) (Time: O(n), Space: O(1))

This approach relies on a core property of palindromes: most characters must appear in pairs, while at most one character in each palindrome can have an odd frequency. Start by counting the frequency of each character using a fixed-size array or hash table. Then count how many characters have odd frequencies. Each odd-frequency character must serve as the center of a palindrome. If the number of odd counts is greater than k, constructing k palindromes is impossible. Also check that len(s) >= k, since every palindrome needs at least one character. This greedy check works because paired characters can always be distributed across palindromes while odd characters determine the minimum number of palindromes required.

Approach 2: Direct Construction Simulation (Time: O(n), Space: O(1) to O(26))

This method simulates how palindromes would actually be built. First compute character frequencies from the string. Assign each odd-frequency character as the center of a palindrome. If the number of such centers exceeds k, construction fails immediately. Otherwise, distribute remaining characters in pairs across the palindromes. Because palindromes mirror characters on both sides, pairs can be added to any existing palindrome without breaking the structure. The algorithm effectively mimics the greedy reasoning while explicitly managing palindrome construction using greedy allocation of pairs.

Recommended for interviews: Character Frequency Counting is the expected solution. Interviewers want you to recognize the palindrome property that odd frequencies determine the minimum number of palindromes. The implementation is short, runs in O(n) time, and uses constant space due to the limited alphabet. The simulation approach demonstrates deeper understanding of palindrome structure but introduces unnecessary steps compared to the direct greedy condition check.

Approach 1: Approach 1: Character Frequency Counting

This approach revolves around counting the frequency of each character in the input string. A valid palindrome can contain at most one character with an odd frequency. Hence, if the number of characters with odd frequencies is greater than k, it is impossible to create k palindrome strings. If it is less than or equal to k, constructing the palindromes is feasible.

Python

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        from collections import Counter
        count = Counter(s)
        odd_count = sum(1 for freq in count.values() if freq % 2 == 1)
        return odd_count <= k <= len(s)

Java

class Solution {
    public boolean canConstruct(String s, int k) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        int oddCount = 0;
        for (int c : count) {
            if (c % 2 == 1) {
                oddCount++;
            }
        }
        return oddCount <= k && k <= s.length();
    }
}

C++

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool canConstruct(string s, int k) {
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        int oddCount = 0;
        for (int c : count) {
            if (c % 2 == 1) {
                oddCount++;
            }
        }
        return oddCount <= k && k <= s.size();
    }
};

JavaScript

var canConstruct = function(s, k) {
    const count = new Array(26).fill(0);
    for (let char of s) {
        count[char.charCodeAt(0) - 97]++;
    }
    let oddCount = 0;
    for (let freq of count) {
        if (freq % 2 === 1) {
            oddCount++;
        }
    }
    return oddCount <= k && k <= s.length;
};

#include <stdbool.h>
#include <string.h>

bool canConstruct(char *s, int k) {
    int count[26] = {0};
    for (int i = 0; s[i]; ++i) {
        count[s[i] - 'a']++;
    }
    int oddCount = 0;
    for (int i = 0; i < 26; ++i) {
        if (count[i] % 2 == 1) {
            oddCount++;
        }
    }
    return oddCount <= k && k <= strlen(s);
}

using System;
using System.Linq;

public class Solution {
    public bool CanConstruct(string s, int k) {
        int[] count = new int[26];
        foreach (char c in s) {
            count[c - 'a']++;
        }
        int oddCount = count.Count(c => c % 2 == 1);
        return oddCount <= k && k <= s.Length;
    }
}

Using Python's collections.Counter, we count character frequencies, then calculate how many have odd frequencies. If this count exceeds k, return false; otherwise, true. This succinct code leverages Python's expressive syntax to simplify logic.

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1) as we store a minor counter object.

Try this approach in the editor

Approach 2: Approach 2: Direct Construction Simulation

This approach seeks a practical simulation of constructing k palindrome strings from the given input string. The idea is to simulate the creation of palindromes in real-time by matching characters from the frequency counts and envisioning the formation of iterative palindromes based on availability and requirement.

Python

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        from collections import Counter
        freq = Counter(s)
        odd_counter = sum(1 for count in freq.values() if count % 2 == 1)
        return odd_counter <= k <= len(s)

Java

class Solution {
    public boolean canConstruct(String s, int k) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        int oddCount = 0;
        for (int c : count) {
            if (c % 2 == 1) {
                oddCount++;
            }
        }
       return oddCount <= k && k <= s.length();
    }
}

C++

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool canConstruct(string s, int k) {
        vector<int> count(26, 0);
        for (char c : s) count[c - 'a']++;
        int oddCount = 0;
        for (int x : count) {
            if (x % 2 != 0) oddCount++;
        }
        return oddCount <= k && k <= s.size();
    }
};

JavaScript

var canConstruct = function(s, k) {
    let freq = new Array(26).fill(0);
    for (let char of s) {
        freq[char.charCodeAt(0) - 97]++;
    }
    let oddCount = freq.filter(x => x % 2 !== 0).length;
    return oddCount <= k && k <= s.length;
};

#include <stdbool.h>
#include <string.h>
#include <stdio.h>

bool canConstruct(char *s, int k) {
    int count[26] = {0}, oddCount = 0;
    int n = strlen(s);
    for (int i = 0; i < n; ++i) {
        count[s[i] - 'a']++; 
    }
    for (int i = 0; i < 26; ++i) {
        oddCount += count[i] % 2;
    }
    return oddCount <= k && k <= n;
}

using System;
using System.Linq;

public class Solution {
    public bool CanConstruct(string s, int k) {
        int[] count = new int[26];
        foreach (char c in s) count[c - 'a']++;
        int oddCount = count.Count(c => c % 2 != 0);
        return oddCount <= k && k <= s.Length;
    }
}

Python's Counter assists in the character frequency count. The solution checks compatibility with the provision of constructing palindromes using simple odd-even logic assessments.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Counting

First, we check if the length of string s is less than k. If it is, we cannot construct k palindrome strings, so we can directly return false.

Otherwise, we use a hash table or an array cnt to count the occurrences of each character in string s. Finally, we only need to count the number of characters x that appear an odd number of times in cnt. If x is greater than k, we cannot construct k palindrome strings, so we return false; otherwise, we return true.

The time complexity is O(n), and the space complexity is O(C). Where n is the length of string s, and C is the size of the character set, here C=26.

TypeScript

function canConstruct(s: string, k: number): boolean {
    if (s.length < k) {
        return false;
    }
    const cnt: number[] = new Array(26).fill(0);
    for (const c of s) {
        ++cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)];
    }
    let x = 0;
    for (const v of cnt) {
        x += v & 1;
    }
    return x <= k;
}

func canConstruct(s string, k int) bool {
	if len(s) < k {
		return false
	}
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
	}
	x := 0
	for _, v := range cnt {
		x += v & 1
	}
	return x <= k
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Character Frequency Counting	Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1) as we store a minor counter object.
Approach 2: Direct Construction Simulation	Time Complexity: O(n) Space Complexity: O(1)
Counting	–

Complexity analysis

Approach	Time	Space	When to Use
Character Frequency Counting (Greedy)	O(n)	O(1)	Best general solution. Quickly checks palindrome feasibility using odd frequency counts.
Direct Construction Simulation	O(n)	O(1) to O(26)	Useful for understanding how characters are distributed when forming palindromes.

Frequently asked questions

Is Construct K Palindrome Strings easy or hard?

Construct K Palindrome Strings is considered a Medium problem on LeetCode. The main challenge is recognizing the palindrome property related to odd character counts. Once that insight is clear, the implementation becomes straightforward and efficient.

Construct K Palindrome Strings Python/Java solution

In Python or Java, the implementation counts character frequencies and checks the number of odd counts. Python often uses collections.Counter, while Java typically uses an int[26] array. Both implementations run in O(n) time and O(1) extra space.

How to solve Construct K Palindrome Strings in O(n)?

Count the frequency of each character in the string. Compute how many characters appear an odd number of times. If the odd count is greater than k, forming k palindromes is impossible; if the string length is less than k, it is also impossible. Otherwise, you can distribute character pairs across palindromes and return true.

What is the best approach for Construct K Palindrome Strings?

The best approach is character frequency counting with a greedy check. Count how many characters have odd frequencies and ensure that number is less than or equal to k, since each palindrome can contain only one odd center. Also verify that the string length is at least k. This runs in O(n) time with O(1) space.

Is Construct K Palindrome Strings asked at Google/Amazon/Meta?

Palindrome construction and frequency counting problems are common in interviews at companies like Amazon, Google, and Meta. Variations of this problem test understanding of string manipulation, greedy reasoning, and counting techniques using hash maps or arrays.

What data structure is used in Construct K Palindrome Strings?

The typical solution uses a frequency array or hash table to count occurrences of each character. Since the problem usually involves lowercase English letters, a fixed array of size 26 is sufficient and provides constant-space performance.

What is the time complexity of Construct K Palindrome Strings?

The optimal solution runs in O(n) time where n is the length of the string. You perform a single pass to count character frequencies and another pass over the frequency array to count odd occurrences. Space complexity is O(1) because the alphabet size is fixed (26 lowercase letters).

Construct K Palindrome Strings solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Character Frequency Counting

Approach 2: Approach 2: Direct Construction Simulation

Approach 3: Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Construct K Palindrome Strings solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Character Frequency Counting

Approach 2: Approach 2: Direct Construction Simulation

Approach 3: Counting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems