Jobs

Interviews

Discussions

Construct K Palindrome Strings

Medium

Construct K Palindrome Strings

Medium

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`?
Can the input string `s` be empty, and if so, what should I return?
If it's impossible to construct `k` palindrome strings from `s`, what should I return (e.g., `false`, throw an exception)?
Does the input string `s` consist only of lowercase English letters, or can it contain other characters?
Do I need to actually construct the k palindrome strings, or simply return whether it's possible to do so?

Brute Force Solution

Approach

The core idea is to check every possible way to divide a given string into smaller strings. We then check if these smaller strings can be rearranged to form palindromes. If we find a valid arrangement we return true, otherwise we try another one.

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

First, consider all possible ways to split the given string into exactly K smaller strings.
For each of these K smaller strings, determine whether it's possible to rearrange the characters to form a palindrome.
A string can be rearranged to form a palindrome if it has at most one character that appears an odd number of times.
If every one of our K smaller strings can form a palindrome then this is a valid solution and we can say it's possible.
If we exhaust all possible ways of splitting the string into K smaller strings, and haven't found a solution, then we return false.

Code Implementation

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

    # If the number of substrings is larger than the string length, impossible
    if k_substrings > string_length:
        return False

    # Function to check if a string can form a palindrome
    def can_form_palindrome(substring):
        character_counts = {}
        for character in substring:
            character_counts[character] = character_counts.get(character, 0) + 1

        odd_count = 0
        for count in character_counts.values():
            if count % 2 != 0:
                odd_count += 1

        return odd_count <= 1

    # Recursive helper function to generate all possible splits
    def find_all_splits(current_index, current_split, all_splits):
        if len(current_split) == k_substrings - 1:
            # Ensure the last substring is added to the split
            last_substring = input_string[current_index:]
            if last_substring:
                current_split.append(last_substring)
                all_splits.append(current_split[:])
                current_split.pop()
            return

        for i in range(current_index + 1, string_length - (k_substrings - 1 - len(current_split)) + 1):
            # Construct substring and add it to the current split
            substring = input_string[current_index:i]
            current_split.append(substring)
            find_all_splits(i, current_split, all_splits)
            current_split.pop()

    all_splits = []
    find_all_splits(0, [], all_splits)

    # Check if any split consists of palindromable substrings
    for split in all_splits:
        can_construct = True
        for substring in split:
            if not can_form_palindrome(substring):
                can_construct = False
                break

        # If all substrings can form a palindrome, we return True
        if can_construct:
            return True

    # If we can't find any valid splits return false
    return False

Big(O) Analysis

Time Complexity

O(2^n) – The dominant factor in the time complexity comes from considering all possible ways to split the string of length n into k substrings. Finding all possible splits involves iterating through all possible combinations of split points. This is equivalent to considering all subsets of a set of (n-1) potential split points, which is O(2^(n-1)). For each split, we iterate through the K substrings (in the worst case K can approach n) and, for each substring, check if it can form a palindrome, which can be done in O(length of substring) time. Given the exponential number of splits, even if palindrome check is efficient, the overall complexity remains O(2^n).

Space Complexity

O(N) – The dominant factor for space complexity stems from considering all possible ways to split the string. While the plain English explanation doesn't detail the *exact* implementation of generating splits, in the worst-case scenario, generating and holding all possible splits might implicitly require storing substrings or indices related to those splits. The maximum number of splits could grow proportionally with the input string length N, causing auxiliary space usage up to O(N) to store such splits or indices. Specifically, each level of the implicit recursion (for exploring different splits) will require storing the currently formed substring, which, in the worst case, could lead to N such substrings. This is especially relevant if the splits are explicitly stored for palindrome checking. Therefore, space complexity is O(N).

Optimal Solution

Approach

The core idea is to understand that a palindrome string can be formed if it either has all even counts of characters or at most one character with an odd count. The strategy is to count how many characters occur an odd number of times and compare that with the desired number of palindrome strings.

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

First, count how many times each character appears in the given string.
Then, count how many characters appear an odd number of times.
If the number of characters appearing an odd number of times is greater than the number of palindrome strings we want to create, then it is impossible to create the desired number of palindromes.
Also, if the length of the string is less than the number of palindrome strings we want to create, it's impossible.
Otherwise, it is possible to create the required number of palindromes.

Code Implementation

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

    odd_count = 0
    for char in character_counts:
        if character_counts[char] % 2 != 0:
            odd_count += 1

    # If odd count is more than k, impossible
    if odd_count > number_of_palindromes:
        return False

    # If length of string is less than k, impossible
    if len(input_string) < number_of_palindromes:
        return False

    # Otherwise, it is possible
    return True

Big(O) Analysis

Time Complexity

O(n) – The solution first iterates through the string of length n to count the frequency of each character. Then, it iterates through these counts (at most 26, since there are only 26 lowercase English letters), which is effectively constant. The dominant operation is the initial frequency count, making the time complexity O(n).

Space Complexity

O(1) – The algorithm primarily uses a character count. Since we are dealing with characters which usually have a fixed size character set (e.g., ASCII or extended ASCII), the space required for character counts will be constant irrespective of the input string's length. The odd count variable is also constant space. Thus, the auxiliary space used is constant, independent of the string's size.

Edge Cases

Case	How to Handle
Null or empty string s	Return False if s is null or empty since no palindromes can be formed.
k is zero or negative	Return False if k is zero or negative as we cannot create zero or negative number of palindromes.
k is greater than the length of string s	Return False because you can never have more palindromes than the length of the string itself (each char being its own palindrome).
String s has length 1 and k is greater than 1	Return False, as you can't break a single character string into more than one palindrome.
String s has length 1 and k is equal to 1	Return True, as a single character is a palindrome.
String s has all unique characters, and k is greater than 1.	Check if the length of s is less than or equal to K since each individual char would be its own palindrome, if not then return false since it is impossible.
String s has length n, and k is equal to n	Return True if k equals the string length, since each character can form its own single-character palindrome.
String s has length n, and k equals 1	Check if the entire string 's' can be a palindrome (if the odd character count is more than 1, then return false).

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`?
Can the input string `s` be empty, and if so, what should I return?
If it's impossible to construct `k` palindrome strings from `s`, what should I return (e.g., `false`, throw an exception)?
Does the input string `s` consist only of lowercase English letters, or can it contain other characters?
Do I need to actually construct the k palindrome strings, or simply return whether it's possible to do so?

Brute Force Solution

Approach

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

First, consider all possible ways to split the given string into exactly K smaller strings.
For each of these K smaller strings, determine whether it's possible to rearrange the characters to form a palindrome.
A string can be rearranged to form a palindrome if it has at most one character that appears an odd number of times.
If every one of our K smaller strings can form a palindrome then this is a valid solution and we can say it's possible.
If we exhaust all possible ways of splitting the string into K smaller strings, and haven't found a solution, then we return false.

Code Implementation

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

    # If the number of substrings is larger than the string length, impossible
    if k_substrings > string_length:
        return False

    # Function to check if a string can form a palindrome
    def can_form_palindrome(substring):
        character_counts = {}
        for character in substring:
            character_counts[character] = character_counts.get(character, 0) + 1

        odd_count = 0
        for count in character_counts.values():
            if count % 2 != 0:
                odd_count += 1

        return odd_count <= 1

    # Recursive helper function to generate all possible splits
    def find_all_splits(current_index, current_split, all_splits):
        if len(current_split) == k_substrings - 1:
            # Ensure the last substring is added to the split
            last_substring = input_string[current_index:]
            if last_substring:
                current_split.append(last_substring)
                all_splits.append(current_split[:])
                current_split.pop()
            return

        for i in range(current_index + 1, string_length - (k_substrings - 1 - len(current_split)) + 1):
            # Construct substring and add it to the current split
            substring = input_string[current_index:i]
            current_split.append(substring)
            find_all_splits(i, current_split, all_splits)
            current_split.pop()

    all_splits = []
    find_all_splits(0, [], all_splits)

    # Check if any split consists of palindromable substrings
    for split in all_splits:
        can_construct = True
        for substring in split:
            if not can_form_palindrome(substring):
                can_construct = False
                break

        # If all substrings can form a palindrome, we return True
        if can_construct:
            return True

    # If we can't find any valid splits return false
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, count how many times each character appears in the given string.
Then, count how many characters appear an odd number of times.
If the number of characters appearing an odd number of times is greater than the number of palindrome strings we want to create, then it is impossible to create the desired number of palindromes.
Also, if the length of the string is less than the number of palindrome strings we want to create, it's impossible.
Otherwise, it is possible to create the required number of palindromes.

Code Implementation

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

    odd_count = 0
    for char in character_counts:
        if character_counts[char] % 2 != 0:
            odd_count += 1

    # If odd count is more than k, impossible
    if odd_count > number_of_palindromes:
        return False

    # If length of string is less than k, impossible
    if len(input_string) < number_of_palindromes:
        return False

    # Otherwise, it is possible
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string s	Return False if s is null or empty since no palindromes can be formed.
k is zero or negative	Return False if k is zero or negative as we cannot create zero or negative number of palindromes.
k is greater than the length of string s	Return False because you can never have more palindromes than the length of the string itself (each char being its own palindrome).
String s has length 1 and k is greater than 1	Return False, as you can't break a single character string into more than one palindrome.
String s has length 1 and k is equal to 1	Return True, as a single character is a palindrome.
String s has all unique characters, and k is greater than 1.	Check if the length of s is less than or equal to K since each individual char would be its own palindrome, if not then return false since it is impossible.
String s has length n, and k is equal to n	Return True if k equals the string length, since each character can form its own single-character palindrome.
String s has length n, and k equals 1	Check if the entire string 's' can be a palindrome (if the odd character count is more than 1, then return false).