Construct K Palindrome Strings - Practice Coding Problems

Construct K Palindrome Strings - Problem

Given a string s and an integer k, determine whether you can use all the characters in s to construct exactly k non-empty palindrome strings.

A palindrome is a string that reads the same forward and backward. Return true if it's possible to construct k palindromes using all characters from s, otherwise return false.

Key constraints:

You must use all characters from the input string
Each palindrome must be non-empty
You need exactly k palindromes

Input & Output

Example 1 — Basic Case

$ Input: s = "annabelle", k = 2

› Output: true

💡 Note: We can construct 2 palindromes: "anna" + "elble" or "anna" + "belle". Only one character 'b' has odd frequency, which is ≤ k=2.

Example 2 — Impossible Case

$ Input: s = "leetcode", k = 3

› Output: false

💡 Note: Characters l, t, c, o, d all have odd frequencies (1 each). That's 5 odd frequencies > k=3, so impossible.

Example 3 — Edge Case

$ Input: s = "yzyzyzyzyzyzy", k = 2

› Output: true

💡 Note: y appears 7 times, z appears 6 times. Only y has odd frequency, so 1 ≤ 2, possible.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

String s and integer k representing desired palindrome count

Process

Count character frequencies and identify odd counts

Output

True if odd frequencies ≤ k, false otherwise

Key Takeaway

🎯 Key Insight: At most k characters can have odd frequencies for k palindromes

Asked in

a Amazon 12 G Google 8

The key insight is that for k palindromes, at most k characters can have odd frequencies. Count character frequencies and check if odd count ≤ k. Best approach is frequency counting. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Backtracking	O(k^n)	O(n)	Try all possible ways to distribute characters into k groups and check if each forms a palindrome
Frequency Counting	O(n)	O(1)	Count character frequencies and check if odd frequencies ≤ k

Brute Force Backtracking — Algorithm Steps

Generate all possible k-partitions of characters
For each partition, check if every group can form a palindrome
Return true if any valid partition exists

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Partitions

Create all possible ways to divide characters into k groups

Check Palindromes

Verify if each group can form a palindrome

Return Result

True if any valid partition exists

Code -

solution.c — C

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

bool canFormPalindrome(char* chars, int len) {
    int count[26] = {0};
    for (int i = 0; i < len; i++) {
        count[chars[i] - 'a']++;
    }
    int oddCount = 0;
    for (int i = 0; i < 26; i++) {
        if (count[i] % 2 == 1) oddCount++;
    }
    return oddCount <= 1;
}

bool backtrack(char* s, int index, char groups[][1001], int groupSizes[], int numGroups, int k, int n) {
    if (index == n) {
        if (numGroups == k) {
            for (int i = 0; i < k; i++) {
                if (!canFormPalindrome(groups[i], groupSizes[i])) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }
    
    // Try existing groups
    for (int i = 0; i < numGroups; i++) {
        groups[i][groupSizes[i]] = s[index];
        groupSizes[i]++;
        if (backtrack(s, index + 1, groups, groupSizes, numGroups, k, n)) {
            return true;
        }
        groupSizes[i]--;
    }
    
    // Try new group
    if (numGroups < k) {
        groups[numGroups][0] = s[index];
        groupSizes[numGroups] = 1;
        if (backtrack(s, index + 1, groups, groupSizes, numGroups + 1, k, n)) {
            return true;
        }
        groupSizes[numGroups] = 0;
    }
    
    return false;
}

bool solution(char* s, int k) {
    int n = strlen(s);
    if (k > n) return false;
    
    char groups[1000][1001];
    int groupSizes[1000] = {0};
    return backtrack(s, 0, groups, groupSizes, 0, k, n);
}

int main() {
    char s[1001];
    int k;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    bool result = solution(s, k);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

Each character can be assigned to any of k groups, creating k^n possibilities

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth and temporary storage for partitions

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

891 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler