Jobs

Interviews

Discussions

Construct K Palindrome Strings

Medium

Amazon

2 views

Topics:

Strings

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.

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⁵

Construct K Palindrome Strings

Medium

Amazon

2 views

Topics:

Strings

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.

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⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the input string `s` and the value of `k`?
Is it possible for the input string `s` to be empty or null?
If it's not possible to construct `k` palindrome strings, should I return `false`, or is there another specific value I should return to indicate failure?
Are there any specific character sets allowed in the string `s` (e.g., only lowercase English letters, or Unicode characters)?
If `k` is greater than the length of the string `s`, is that considered a valid case? What should I return?

Brute Force Solution

Approach

The goal is to see if a string can be split into a certain number of palindromic parts. The brute force way to do this is to try every possible way to split the string and then check if each part is a palindrome.

Here's how the algorithm would work step-by-step:

First, consider every possible way to divide the string into the specified number of parts.
For each possible division, check if each part is a palindrome (reads the same forwards and backward).
If all parts in a division are palindromes, then this division is a valid solution.
If we find at least one valid solution (where all parts are palindromes), then we can successfully construct the desired number of palindrome strings from the original string. Otherwise, we cannot.

Code Implementation

def can_construct_k_palindromes_brute_force(input_string, num_palindromes):
    string_length = len(input_string)

    # If we need more palindromes than the length of the string,
    # it's impossible to construct them.
    if num_palindromes > string_length:
        return False

    def is_palindrome(substring):
        return substring == substring[::-1]

    def can_split_into_palindromes(current_index, palindromes_formed, current_partition):
        # Base case: If we've reached the end of the string and
        # formed the desired number of palindromes.
        if current_index == string_length:
            if len(palindromes_formed) == num_palindromes:
                return True
            else:
                return False

        # Explore all possible partitions starting from the current index.
        for next_index in range(current_index + 1, string_length + 1):
            substring = input_string[current_index:next_index]

            # Check if the current substring is a palindrome.
            if is_palindrome(substring):
                # If it is, explore the possibility of including it in our partition.
                if can_split_into_palindromes(next_index, palindromes_formed + [substring], current_partition + [substring]):
                    return True

        return False

    # Start the recursive process to check if string can be partitioned.
    return can_split_into_palindromes(0, [], [])

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n * 2^ (n-1)) – The dominating factor in the brute force approach is generating all possible ways to divide the string into k substrings. For a string of length n, there are n-1 possible split points. Each split point can either be a split or not a split, leading to 2^(n-1) possible combinations. For each of these combinations, we need to iterate through all substrings (at most n of them) to verify if each is a palindrome, which takes O(n) time per string in the worst case. Therefore, the overall time complexity is O(n * 2^(n-1)), dominated by generating and validating each of the exponential number of substring combinations.

Space Complexity

O(N) – The brute force approach described requires checking every possible way to split the string. While the plain English description does not explicitly mention storing all possible divisions simultaneously, implicit space is used. The number of possible divisions will scale proportionally to the length of the string (N). Since we are evaluating a potentially large number of substrings and their palindromic nature, auxiliary space for copies or temporary storage of substring is required, scaling linearly with N. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The key insight is that we can figure out if a solution is even possible by looking at the counts of each letter. If a solution *is* possible, we can simply assign each odd-count character to its own palindrome string. Then we can pad these with pairs of even-count characters to make the required number of strings.

Here's how the algorithm would work step-by-step:

Count how many times each letter appears in the input string.
Figure out how many letters appear an odd number of times.
If the number of odd-count letters is bigger than the number of palindrome strings we need to create, it's impossible to make the strings. Return false in this case.
If the number of odd-count letters is less than or equal to the number of palindrome strings we need to create, it's possible to make the strings. Return true in this case.

Code Implementation

def canConstruct(input_string: str, number_of_palindromes: int) -> bool:
    letter_counts = {}
    for letter in input_string:
        letter_counts[letter] = letter_counts.get(letter, 0) + 1

    odd_count_letters = 0
    for letter in letter_counts:
        if letter_counts[letter] % 2 != 0:
            odd_count_letters += 1

    # If too many odd counts, impossible to construct.
    if odd_count_letters > number_of_palindromes:
        return False

    # Enough or fewer odd counts means construction is possible.
    # Each odd-count character makes its own palindrome.
    if odd_count_letters <= number_of_palindromes:
        return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The solution first counts the frequency of each character in the input string s of length n. This involves iterating through the string once, resulting in O(n) time complexity. Then, it counts the number of characters with odd frequencies, which takes at most O(26) = O(1) time since there are only 26 possible lowercase English letters. Finally, the algorithm compares the number of odd-count letters with k, which is O(1). Therefore, the dominant operation is the character frequency counting, making the overall time complexity O(n).

Space Complexity

O(1) – The solution uses a fixed-size array or hash map to count letter frequencies. Since there are a fixed number of possible characters (e.g., 26 for lowercase English letters), the size of this data structure remains constant irrespective of the input string's length N. No other data structures whose size depends on N are used. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Empty string s and k > 0	Return false because you cannot create non-empty palindrome strings from an empty string.
Non-empty string s and k = 0	Return false because you need to create at least one palindrome string.
String s has length n and k > n	Return false because you cannot create more palindrome strings than characters in s (each palindrome must have at least one character).
String s has length n and k = n	Return true if each character in s is unique, as each character can form a palindrome of length 1; otherwise, return false.
String s has all identical characters and k > 1	Return false because if all characters are identical, you can only form one palindrome string.
String s is very long and contains many different characters.	The character count should be done efficiently (O(n) time and O(1) space since alphabet size is constant).
String s contains unicode characters.	The character count should correctly handle unicode characters using a suitable data structure (e.g., a hash map capable of storing unicode characters as keys).
k = 1 and s is a non-empty string.	Return true, because any string can be considered as a palindrome of length n.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the input string `s` and the value of `k`?
Is it possible for the input string `s` to be empty or null?
If it's not possible to construct `k` palindrome strings, should I return `false`, or is there another specific value I should return to indicate failure?
Are there any specific character sets allowed in the string `s` (e.g., only lowercase English letters, or Unicode characters)?
If `k` is greater than the length of the string `s`, is that considered a valid case? What should I return?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider every possible way to divide the string into the specified number of parts.
For each possible division, check if each part is a palindrome (reads the same forwards and backward).
If all parts in a division are palindromes, then this division is a valid solution.
If we find at least one valid solution (where all parts are palindromes), then we can successfully construct the desired number of palindrome strings from the original string. Otherwise, we cannot.

Code Implementation

def can_construct_k_palindromes_brute_force(input_string, num_palindromes):
    string_length = len(input_string)

    # If we need more palindromes than the length of the string,
    # it's impossible to construct them.
    if num_palindromes > string_length:
        return False

    def is_palindrome(substring):
        return substring == substring[::-1]

    def can_split_into_palindromes(current_index, palindromes_formed, current_partition):
        # Base case: If we've reached the end of the string and
        # formed the desired number of palindromes.
        if current_index == string_length:
            if len(palindromes_formed) == num_palindromes:
                return True
            else:
                return False

        # Explore all possible partitions starting from the current index.
        for next_index in range(current_index + 1, string_length + 1):
            substring = input_string[current_index:next_index]

            # Check if the current substring is a palindrome.
            if is_palindrome(substring):
                # If it is, explore the possibility of including it in our partition.
                if can_split_into_palindromes(next_index, palindromes_formed + [substring], current_partition + [substring]):
                    return True

        return False

    # Start the recursive process to check if string can be partitioned.
    return can_split_into_palindromes(0, [], [])

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Count how many times each letter appears in the input string.
Figure out how many letters appear an odd number of times.
If the number of odd-count letters is bigger than the number of palindrome strings we need to create, it's impossible to make the strings. Return false in this case.
If the number of odd-count letters is less than or equal to the number of palindrome strings we need to create, it's possible to make the strings. Return true in this case.

Code Implementation

def canConstruct(input_string: str, number_of_palindromes: int) -> bool:
    letter_counts = {}
    for letter in input_string:
        letter_counts[letter] = letter_counts.get(letter, 0) + 1

    odd_count_letters = 0
    for letter in letter_counts:
        if letter_counts[letter] % 2 != 0:
            odd_count_letters += 1

    # If too many odd counts, impossible to construct.
    if odd_count_letters > number_of_palindromes:
        return False

    # Enough or fewer odd counts means construction is possible.
    # Each odd-count character makes its own palindrome.
    if odd_count_letters <= number_of_palindromes:
        return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string s and k > 0	Return false because you cannot create non-empty palindrome strings from an empty string.
Non-empty string s and k = 0	Return false because you need to create at least one palindrome string.
String s has length n and k > n	Return false because you cannot create more palindrome strings than characters in s (each palindrome must have at least one character).
String s has length n and k = n	Return true if each character in s is unique, as each character can form a palindrome of length 1; otherwise, return false.
String s has all identical characters and k > 1	Return false because if all characters are identical, you can only form one palindrome string.
String s is very long and contains many different characters.	The character count should be done efficiently (O(n) time and O(1) space since alphabet size is constant).
String s contains unicode characters.	The character count should correctly handle unicode characters using a suitable data structure (e.g., a hash map capable of storing unicode characters as keys).
k = 1 and s is a non-empty string.	Return true, because any string can be considered as a palindrome of length n.