Jobs

Interviews

Discussions

Palindrome Partitioning

Medium

Palindrome Partitioning

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 is the maximum length of the input string, and are there any associated performance expectations?
Can the input string be empty or null? If so, what should the function return in those cases?
If there are multiple possible palindrome partitionings, does the order of the partitions within the result matter? Should I return all possible partitionings, and if so, in what order?
Are we considering only contiguous palindromic substrings, or can the partitioning use non-contiguous palindromes?
Are there any special characters or non-ASCII characters in the input string that I should be aware of?

Brute Force Solution

Approach

The problem asks us to split a given sentence into multiple smaller sentences, where each small sentence reads the same forwards and backward (is a palindrome). The brute force approach tries every conceivable way to make these splits. We're checking every single combination to see if it works.

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

Start by considering the first possible split: no split at all, which means the entire sentence is one possible first palindrome.
Then, consider splitting the sentence after the first letter. Check if the first letter itself is a palindrome. If so, we can move on to find palindromic splits for the remainder of the sentence.
Next, consider splitting the sentence after the second letter. Check if the first two letters together form a palindrome. If so, again we move on to the remainder.
Keep doing this, each time moving the split point one letter further along. For each possible 'first' palindrome you find, you then repeat this whole process for the remaining part of the sentence.
Keep repeating this division process until you have looked at every possible combination of palindromic splits for the whole sentence.
After exploring every combination, identify the ones where every part is actually a palindrome. Then select the combination of palindromic splits that satisfies the problem conditions (e.g., the smallest number of partitions).

Code Implementation

def palindrome_partitioning_brute_force(input_string):
    result = []
    number_of_chars = len(input_string)

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

    def find_all_partitions(start_index, current_partition):
        if start_index >= number_of_chars:
            result.append(current_partition[:])
            return

        # Iterate through all possible ending points
        for end_index in range(start_index, number_of_chars):
            substring = input_string[start_index : end_index + 1]

            # Check if the substring is a palindrome
            if is_palindrome(substring):

                # Add the palindrome to the current partition
                current_partition.append(substring)

                # Recursively find partitions for the remaining string
                find_all_partitions(end_index + 1, current_partition)

                # Backtrack to explore other possibilities
                current_partition.pop()

    find_all_partitions(0, [])
    return result

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible partitions of the string. For a string of length n, there are 2^(n-1) possible ways to partition it (each position between characters can either be a split or not). For each of these partitions, we need to verify if each substring is a palindrome, which takes O(n) time in the worst case to check each partition. Therefore, the overall time complexity is O(n * 2^(n-1)). Simplifying this gives O(2^n).

Space Complexity

O(N) – The algorithm uses recursion to explore all possible palindrome partitions. In the worst-case scenario, the recursion depth can be N, where N is the length of the input string, as we might consider splitting after each character. Each recursive call requires a new stack frame to store local variables and the return address. Thus, the auxiliary space used by the call stack can grow linearly with the input size, resulting in O(N) space complexity.

Optimal Solution

Approach

The goal is to break a word into smaller parts, where each part reads the same forwards and backward. The most efficient way to do this involves figuring out which parts are palindromes early on, then using that knowledge to quickly explore possible groupings.

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

First, figure out all the palindrome parts of the big word. We do this by checking every possible piece and marking the ones that are palindromes.
Once we know all the palindrome parts, we can start dividing the big word.
We go through the big word from start to finish. At each spot, we look at all the palindrome parts that start at that spot.
For each of those palindrome parts, we make a note that says 'we can divide the big word up to here'.
We keep going until we reach the end of the big word. If we can divide the big word all the way to the end, we found a way to split it into palindromes.
To actually find the different ways to split it, we trace back our steps, remembering where we made each split.
By figuring out the palindrome parts first, we avoid repeating work and find all the correct ways to split the big word quickly.

Code Implementation

def palindrome_partitioning(input_string):
    string_length = len(input_string)
    palindrome_substrings = [[False] * string_length for _ in range(string_length)]

    # Identify all palindrome substrings.
    for substring_length in range(1, string_length + 1):
        for start_index in range(string_length - substring_length + 1):
            end_index = start_index + substring_length - 1
            if substring_length == 1:
                palindrome_substrings[start_index][end_index] = True
            elif substring_length == 2:
                palindrome_substrings[start_index][end_index] = (input_string[start_index] == input_string[end_index])
            else:
                palindrome_substrings[start_index][end_index] = (input_string[start_index] == input_string[end_index]) and palindrome_substrings[start_index + 1][end_index - 1]

    result_partitions = []
    current_partition = []

    def backtrack(start_index):
        # If the partition reaches the end, add it to results.
        if start_index == string_length:
            result_partitions.append(current_partition[:])
            return

        # Iterate through possible substrings.
        for end_index in range(start_index, string_length):
            if palindrome_substrings[start_index][end_index]:
                substring = input_string[start_index:end_index + 1]

                # Explore partitioning with the current palindrome.
                current_partition.append(substring)

                backtrack(end_index + 1)

                # Backtrack to explore other possibilities.
                current_partition.pop()

    # Initiate backtracking from the beginning of the string.
    backtrack(0)
    return result_partitions

Big(O) Analysis

Time Complexity

O(n²) – The first step is identifying all palindromic substrings. This involves iterating through all possible substrings of the input string of length n. For each starting position (of which there are n), we can have substrings up to length n. Therefore, the palindrome check potentially examines n * n substrings. Since checking if a substring is a palindrome takes O(n) time in the worst case, this step contributes O(n³) to the overall complexity. However, the explanation assumes a precomputed table which makes the palindrome check O(1), and thus makes the palindrome identification O(n²). The subsequent steps that trace back the results take no more than O(n²) time.

Space Complexity

O(N^2) – The algorithm first identifies all palindrome substrings. To store whether each substring is a palindrome, a two-dimensional boolean array (or similar structure) of size N x N is used, where N is the length of the input string. This array represents all possible substrings and whether they are palindromes. Additionally, during the partitioning and backtracking steps, we may need to store intermediate results and possible partitions in a list which in the worst case might store lists of length N. Therefore, the auxiliary space is dominated by the N x N palindrome table, resulting in O(N^2) space complexity.

Edge Cases

Case	How to Handle
Empty string input	Return an empty list since there are no partitions to generate.
Null string input	Return null or throw an IllegalArgumentException, depending on the API contract.
String with a single character	Return a list containing a single list with the single character as a palindrome.
String with all identical characters (e.g., 'aaaa')	Generates many valid partitions, potentially leading to performance issues if not optimized correctly.
Very long string to test for stack overflow with recursive solutions	Consider using dynamic programming to avoid excessive recursion depth if performance is a concern.
String that is already a palindrome (e.g., 'madam')	The solution should correctly identify the entire string as a single valid partition.
String with no palindromic substrings longer than 1 character (e.g., 'abcde')	The solution should generate all possible partitions where each substring is a single character.
String with mixed uppercase and lowercase letters	Consider whether the palindrome check should be case-sensitive or case-insensitive and normalize the string if needed.

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 is the maximum length of the input string, and are there any associated performance expectations?
Can the input string be empty or null? If so, what should the function return in those cases?
If there are multiple possible palindrome partitionings, does the order of the partitions within the result matter? Should I return all possible partitionings, and if so, in what order?
Are we considering only contiguous palindromic substrings, or can the partitioning use non-contiguous palindromes?
Are there any special characters or non-ASCII characters in the input string that I should be aware of?

Brute Force Solution

Approach

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

Start by considering the first possible split: no split at all, which means the entire sentence is one possible first palindrome.
Then, consider splitting the sentence after the first letter. Check if the first letter itself is a palindrome. If so, we can move on to find palindromic splits for the remainder of the sentence.
Next, consider splitting the sentence after the second letter. Check if the first two letters together form a palindrome. If so, again we move on to the remainder.
Keep doing this, each time moving the split point one letter further along. For each possible 'first' palindrome you find, you then repeat this whole process for the remaining part of the sentence.
Keep repeating this division process until you have looked at every possible combination of palindromic splits for the whole sentence.
After exploring every combination, identify the ones where every part is actually a palindrome. Then select the combination of palindromic splits that satisfies the problem conditions (e.g., the smallest number of partitions).

Code Implementation

def palindrome_partitioning_brute_force(input_string):
    result = []
    number_of_chars = len(input_string)

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

    def find_all_partitions(start_index, current_partition):
        if start_index >= number_of_chars:
            result.append(current_partition[:])
            return

        # Iterate through all possible ending points
        for end_index in range(start_index, number_of_chars):
            substring = input_string[start_index : end_index + 1]

            # Check if the substring is a palindrome
            if is_palindrome(substring):

                # Add the palindrome to the current partition
                current_partition.append(substring)

                # Recursively find partitions for the remaining string
                find_all_partitions(end_index + 1, current_partition)

                # Backtrack to explore other possibilities
                current_partition.pop()

    find_all_partitions(0, [])
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, figure out all the palindrome parts of the big word. We do this by checking every possible piece and marking the ones that are palindromes.
Once we know all the palindrome parts, we can start dividing the big word.
We go through the big word from start to finish. At each spot, we look at all the palindrome parts that start at that spot.
For each of those palindrome parts, we make a note that says 'we can divide the big word up to here'.
We keep going until we reach the end of the big word. If we can divide the big word all the way to the end, we found a way to split it into palindromes.
To actually find the different ways to split it, we trace back our steps, remembering where we made each split.
By figuring out the palindrome parts first, we avoid repeating work and find all the correct ways to split the big word quickly.

Code Implementation

def palindrome_partitioning(input_string):
    string_length = len(input_string)
    palindrome_substrings = [[False] * string_length for _ in range(string_length)]

    # Identify all palindrome substrings.
    for substring_length in range(1, string_length + 1):
        for start_index in range(string_length - substring_length + 1):
            end_index = start_index + substring_length - 1
            if substring_length == 1:
                palindrome_substrings[start_index][end_index] = True
            elif substring_length == 2:
                palindrome_substrings[start_index][end_index] = (input_string[start_index] == input_string[end_index])
            else:
                palindrome_substrings[start_index][end_index] = (input_string[start_index] == input_string[end_index]) and palindrome_substrings[start_index + 1][end_index - 1]

    result_partitions = []
    current_partition = []

    def backtrack(start_index):
        # If the partition reaches the end, add it to results.
        if start_index == string_length:
            result_partitions.append(current_partition[:])
            return

        # Iterate through possible substrings.
        for end_index in range(start_index, string_length):
            if palindrome_substrings[start_index][end_index]:
                substring = input_string[start_index:end_index + 1]

                # Explore partitioning with the current palindrome.
                current_partition.append(substring)

                backtrack(end_index + 1)

                # Backtrack to explore other possibilities.
                current_partition.pop()

    # Initiate backtracking from the beginning of the string.
    backtrack(0)
    return result_partitions

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	Return an empty list since there are no partitions to generate.
Null string input	Return null or throw an IllegalArgumentException, depending on the API contract.
String with a single character	Return a list containing a single list with the single character as a palindrome.
String with all identical characters (e.g., 'aaaa')	Generates many valid partitions, potentially leading to performance issues if not optimized correctly.
Very long string to test for stack overflow with recursive solutions	Consider using dynamic programming to avoid excessive recursion depth if performance is a concern.
String that is already a palindrome (e.g., 'madam')	The solution should correctly identify the entire string as a single valid partition.
String with no palindromic substrings longer than 1 character (e.g., 'abcde')	The solution should generate all possible partitions where each substring is a single character.
String with mixed uppercase and lowercase letters	Consider whether the palindrome check should be case-sensitive or case-insensitive and normalize the string if needed.