1400. Construct K Palindrome Strings

MediumGreedyHash TableStringCounting

Problem Description

The LeetCode problem asks us to determine if we can construct k palindromic strings using all the characters of a given string s. A palindrome is a word or phrase that reads the same forwards and backwards. The constraint is that we must use every character in s exactly once to create these k palindromes. If we can achieve this, we return true. Otherwise, we return false.

To put it simply, we want to know if the characters in s can be rearranged in a way that they form k separate palindromes. It's important to remember that the lengths of the palindromes can vary, and they do not need to be all of the same length.

Intuition

To solve this problem, we need to understand the characteristics of palindromes:

Even-count characters can be used entirely to form palindromes as they can be symmetrically placed around the center. For example, 'aabb' can be used to form the palindrome 'abba'.
Odd-count characters have a different constraint. At most, one character with an odd count can be in the center of a palindrome (for example, 'racecar' where 'e' is in the middle), and all others must be paired to maintain symmetry.
Given these properties, if k is greater than the length of s, we cannot form k non-empty palindromes.

The intuition behind the solution focuses on points 1 and 2:

First, we need to know if there are enough characters in s to form k palindromes. We achieve this by comparing the length of s to k. If s is shorter than k, we cannot form k palindromes, so we return false.
Next, we count how many characters have an odd count because each odd-count character can be the center of a palindrome only once. This means the number of palindromes we can create is limited by the number of characters with odd counts, as every palindrome can only have one center character.
We then check if the number of odd-count characters is less than or equal to k because if there are more odd-count characters than k, we can't place them at the center of each palindrome, and thus can't create k valid palindromes.
If the number of odd-count characters is less than or equal to k, we can always rearrange the characters to create the required palindromes, so we return true.

The solution makes use of Python's Counter class from the collections module to count the instances of each character in s. The expression v & 1 is a bitwise operation checking if the count v is odd (since odd numbers have the lowest bit set to 1). The summation counts how many characters have odd occurrences, and finally, this count is compared to k.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First SearchBreadth-First SearchBinary SearchPriority Queue

I don’t know

Solution Approach

The solution approach follows a well-defined set of steps that leverage a few Python-specific tools as well as some general algorithmic concepts.

Here is a breakdown of the implementation:

Check Length Against k: We start by comparing the length of the string s to the integer k. If len(s) is less than k, we immediately return false because you cannot construct more non-empty palindromic strings than the number of available characters.
```
1if len(s) < k:
2    return False
```
Count Characters with Counter: Next, we use the Counter class from the collections module of Python. This is a subclass of the dictionary which is designed to count hashable objects (like characters in a string). It helps in finding the frequency of each character in s.
```
1cnt = Counter(s)
```
Count Odd-Occurrence Characters: We then proceed to calculate the number of characters that appear an odd number of times in the string. To find out if the count v is odd, we use the bitwise AND (&) operation with 1. If v & 1 yields 1, the count is odd. This trick works because in binary representation the least significant bit determines the oddness of a number. Summing these up gives us the total number of odd-count characters.
```
1sum(v & 1 for v in cnt.values())
```
The comprehension iterates over the counts of each character obtained from Counter. Each value is checked for oddness, and then they are summed together to get a total count of characters that have to be placed in the center of a palindrome.
Compare Odd Count to k: Lastly, the implementation compares the number of odd-count characters to k. As mentioned before in the intuition, if the sum of odd-count characters is less than or equal to k, it is possible to form k palindromic strings using all the characters of s. Otherwise, it's not feasible.
```
1return sum(v & 1 for v in cnt.values()) <= k
```

By understanding that each palindrome can only have one odd-count character at its center, the solution efficiently validates the possibility of creating the k palindromic strings. There is no need to actually construct the palindromes, only to ensure the conditions for their existence are met. This approach leads to a time complexity of O(n), where n is the length of the string s, which is the time required to count the frequency of each character.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's consider an example with string s = "aaabbbcc" and k = 2.

Step 1: Check Length Against `k`

First, we compare the length of s with k. Since len("aaabbbcc") is 8, which is greater than k (which is 2), we can proceed. If the string s was shorter than k, we wouldn't have enough characters to form k non-empty palindromic strings, and the function would return false immediately.

Step 2: Count Characters with `Counter`

We count the frequency of each character in the string s:

'a' appears 3 times
'b' appears 3 times
'c' appears 2 times

Step 3: Count Odd-Occurrence Characters

From our counts, we can see that 'a' and 'b' have odd occurrences (3 times each), while 'c' is even. There are two characters ('a' and 'b') that have an odd count.

Step 4: Compare Odd Count to `k`

Since we have 2 odd-count characters ('a' and 'b'), and k is also 2, this fulfills the requirement that we can have at most one odd-count character at the center of a palindrome. Therefore, we can potentially form 2 palindromes, one with 'a' at the center and one with 'b' at the center, using 'c' to complete both palindromes since it has an even count.

Here, sum(v & 1 for v in cnt.values()) equals 2, which is <= k. Thus, the final comparison is true.

Based on these steps, we could rearrange 'aaabbbcc' into two palindromic strings such as 'abcba' and 'acbca', so the function should return true.

This example illustrates the solution approach step-by-step and confirms the possibility of forming k palindromic strings using all characters of s.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def canConstruct(self, string: str, num_partitions: int) -> bool:
5        # If the length of the string is less than the required number of partitions, 
6        # we cannot construct the required partitions, so return False.
7        if len(string) < num_partitions:
8            return False
9      
10        # Count the frequency of each character in the string using Counter.
11        char_counter = Counter(string)
12
13        # Calculate the number of characters that have an odd count.
14        # This loop goes through the values (counts) in the char_counter
15        # and uses a bitwise AND operation (&) with 1 to determine if the count is odd.
16        odd_count = sum(count & 1 for count in char_counter.values())
17
18        # The number of characters with odd counts should not exceed the number
19        # of partitions we want to create, because each palindrome must have at most
20        # one character with an odd count (in the middle). Therefore, if we have
21        # no more odd counts than the number of partitions, we can construct the palindromes.
22        return odd_count <= num_partitions
23

1class Solution {
2    public boolean canConstruct(String inputString, int palindromeCount) {
3        // Length of the input string
4        int length = inputString.length();
5      
6        // If the input string is shorter than the required number of palindromes,
7        // it is not possible to construct the palindromes.
8        if (length < palindromeCount) {
9            return false;
10        }
11      
12        // Array to hold the count of each character in the inputString.
13        int[] characterFrequency = new int[26];
14      
15        // Count the frequency of each character in the inputString.
16        for (int i = 0; i < length; ++i) {
17            characterFrequency[inputString.charAt(i) - 'a']++;
18        }
19      
20        // Count the number of characters that appear an odd number of times.
21        int oddCount = 0;
22        for (int frequency : characterFrequency) {
23            oddCount += frequency % 2;
24        }
25      
26        // It is possible to form palindromes if the number of characters with
27        // odd frequency is less than or equal to the number of palindromes we need to construct.
28        return oddCount <= palindromeCount;
29    }
30}
31

1class Solution {
2public:
3    // Method to determine if a string s can be rearranged to form exactly k palindromic substrings.
4    bool canConstruct(string s, int k) {
5        // If the size of s is less than k, it's not possible to construct k palindromes
6        if (s.size() < k) {
7            return false;
8        }
9
10        // Array to store the frequency of each letter in the string
11        int letterCount[26] = {0};
12        // Count the frequency of each character in s
13        for (char& c : s) {
14            ++letterCount[c - 'a'];
15        }
16
17        // Variable to keep track of the number of characters with odd frequency
18        // (which determines how many palindromes can be made)
19        int oddCount = 0;
20        // Check the letter frequencies
21        for (int count : letterCount) {
22            // If the count is odd, increment oddCount
23            oddCount += count & 1;
24        }
25
26        // A palindrome can accommodate one odd count character (the middle one), so if there
27        // are more odd count characters than k, it's not possible to create k palindromes.
28        // hence, we return whether the oddCount is less than or equal to k.
29        return oddCount <= k;
30    }
31};
32

1function canConstruct(s: string, k: number): boolean {
2    // Early return if the string's length is less than k
3    if (s.length < k) {
4        return false;
5    }
6
7    // Initialize an array to hold the frequency of each character
8    const frequency: number[] = new Array(26).fill(0);
9  
10    // Populate the frequency array with counts for each character in the string
11    for (const char of s) {
12        frequency[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
13    }
14
15    // Counter for the number of characters having odd frequency
16    let oddCount = 0;
17  
18    // Calculate the number of characters with odd frequency
19    for (const count of frequency) {
20        if (count % 2 !== 0) {
21            oddCount++;
22        }
23    }
24  
25    // A string can be constructed if the number of odd-frequency characters
26    // is less than or equal to k (since each odd count character can start a new palindrome)
27    return oddCount <= k;
28}
29

Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by a few operations:

len(s): This operation takes O(n) where n is the length of the string s.
Counter(s): Counting the frequency of each character in the string takes O(n) since it goes through the string once.
sum(v & 1 for v in cnt.values()): This operation iterates over the values in the counter, which in the worst case are as many as n, and performs a bitwise AND and summing operation. The iteration is O(n) and the bitwise AND and summation are O(1) per operation.

Combining these, the overall time complexity is O(n).

Space Complexity

The space complexity is also determined by the data structures and operations used:

Counter(s): The counter object stores character counts, and in the worst case, if all characters are unique, it could store n key-value pairs. Hence, the space complexity is O(n).

Overall, the space complexity of the given code is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1400. Construct K Palindrome Strings

Problem Description

Intuition

Solution Approach

Example Walkthrough

Step 1: Check Length Against k

Step 2: Count Characters with Counter

Step 3: Count Odd-Occurrence Characters

Step 4: Compare Odd Count to k

Solution Implementation

Time and Space Complexity

Step 1: Check Length Against `k`

Step 2: Count Characters with `Counter`

Step 4: Compare Odd Count to `k`