Jobs

Interviews

Discussions

Longest Chunked Palindrome Decomposition

Hard

Asked by:

17 views

Topics:

StringsGreedy AlgorithmsTwo Pointers

You are given a string text. You should split it to k substrings (subtext₁, subtext₂, ..., subtext_k) such that:

subtext_i is a non-empty string.
The concatenation of all the substrings is equal to text (i.e., subtext₁ + subtext₂ + ... + subtext_k == text).
subtext_i == subtext_{k - i + 1} for all valid values of i (i.e., 1 <= i <= k).

Return the largest possible value of k.

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a)".

Constraints:

1 <= text.length <= 1000
text consists only of lowercase English characters.

Try coding it in LeetCode

Longest Chunked Palindrome Decomposition

Hard

Asked by:

17 views

Topics:

StringsGreedy AlgorithmsTwo Pointers

You are given a string text. You should split it to k substrings (subtext₁, subtext₂, ..., subtext_k) such that:

subtext_i is a non-empty string.
The concatenation of all the substrings is equal to text (i.e., subtext₁ + subtext₂ + ... + subtext_k == text).
subtext_i == subtext_{k - i + 1} for all valid values of i (i.e., 1 <= i <= k).

Return the largest possible value of k.

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a)".

Constraints:

1 <= text.length <= 1000
text consists only of lowercase English characters.

Try coding it in LeetCode

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:

Can the input string be empty or null?
What is the maximum length of the input string?
If the string cannot be decomposed into palindrome chunks, what should I return?
Are the palindrome chunks required to be non-overlapping?
Can you provide a specific example of a string and its expected decomposition to confirm my understanding?

Brute Force Solution

Approach

The brute force method for this puzzle involves trying every conceivable way to chop the string into matching pieces. We want to find the largest number of pieces that make up a palindrome when arranged in a specific way. The method will attempt every partition combination to find the best one.

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

Start by seeing if the entire string is a palindrome. If it is, we're done; the answer is one piece.
Next, try cutting off one character from the beginning and one character from the end. Check if these two single-character pieces are equal. If they are, that's two pieces, and we now have a smaller string in the middle to work with.
Then, try cutting off two characters from the beginning and two from the end. See if these two-character chunks are equal. If they are, that's two pieces, and we now have a smaller string in the middle.
Keep increasing the size of the chunks you cut off from both ends and check if they match. If they do, count them as two pieces and recursively apply the same process on the inner remaining string.
If no chunks match in a particular try, it means that the string cannot be further decomposed and we need to backtrack and try out other combinations by changing the length of the initial chunks.
Keep track of the maximum number of matching chunk pairs found through all the tried-out combinations and that would be our desired answer.

Code Implementation

def longest_chunked_palindrome_decomposition_brute_force(text):
    if not text:
        return 0

    if text == text[::-1]:
        return 1

    maximum_chunks = 1
    for chunk_length in range(1, len(text) // 2 + 1):
        # Check all possible chunk lengths
        if text[:chunk_length] == text[-chunk_length:]:

            # Recursively decompose remaining string
            remaining_text = text[chunk_length:-chunk_length]

            maximum_chunks = max(
                maximum_chunks,
                2 + longest_chunked_palindrome_decomposition_brute_force(remaining_text),
            )

    return maximum_chunks

Big(O) Analysis

Time Complexity

O(n^2) – The described approach explores all possible chunk decompositions of the input string of length n. In the worst case, for each possible chunk size from 1 to n/2, we might compare prefixes and suffixes. Within each comparison, we have to iterate through the characters of the chunk being compared, and potentially recurse on the remaining middle substring. This leads to roughly (n/2) * n operations in the worst case, where n/2 comes from the maximum possible chunk sizes and n represents the comparisons and potential recursive calls within each chunk comparison. Thus, the overall time complexity is O(n^2).

Space Complexity

O(N) – The primary driver of space complexity is the recursive calls. In the worst-case scenario, where no matching chunks are found except for single-character chunks, the function will recursively call itself with substrings that are only two characters shorter each time. This will lead to a maximum recursion depth proportional to N/2, where N is the length of the input string. Each recursive call creates a new stack frame, thus the auxiliary space required grows linearly with N. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The goal is to break the string into the largest number of palindrome chunks. We achieve this by greedily matching chunks from the beginning and end of the string, working our way inwards. This avoids unnecessary checks and finds the optimal solution quickly.

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

Compare the beginning of the string with the end of the string.
If the beginning and end match, consider this as one palindrome chunk, and remove those matched parts from both ends.
Repeat this process, each time shortening the string from both sides.
If the beginning and end *don't* match, shorten the end of the string by one character and try comparing again.
Continue shrinking the end until a match is found, or the shrinking part becomes empty.
Keep repeating this process, matching and removing chunks from both ends until the remaining part in the middle is either empty, or cannot be further divided.
If there's any remaining part in the middle that can't be divided, it counts as one last palindrome chunk.
The total number of chunks is the number of matched pairs plus one (if there's a remaining middle part).

Code Implementation

def longestDecomposition(text): 
    left_index = 0
    right_index = len(text) - 1
    chunk_count = 0

    while left_index <= right_index:
        sub_length = 1
        while left_index + sub_length - 1 < right_index - sub_length + 1:
            # Increment sub_length to find the largest possible match.
            sub_length += 1

        while sub_length > 0:
            left_substring = text[left_index:left_index + sub_length]
            right_substring = text[right_index - sub_length + 1:right_index + 1]

            # Greedily match substrings from the beginning and end.
            if left_substring == right_substring:
                chunk_count += 2
                left_index += sub_length
                right_index -= sub_length
                break
            else:
                sub_length -= 1

        # If no match is found, the remaining middle part is a chunk.
        if sub_length == 0:
            chunk_count += 1
            break

    return chunk_count

Big(O) Analysis

Time Complexity

O(n^2) – The outer implicit 'loop' iterates roughly n/2 times in the worst case, as the string shrinks from both ends. Inside this, the substring comparison in step 4 can take up to n/2 time in the worst case for each outer 'loop' iteration since it potentially needs to shrink the end substring one character at a time until a match is found or the substring becomes empty. Thus, the overall time complexity is approximately (n/2)*(n/2), which simplifies to O(n^2).

Space Complexity

O(N) – The plain English explanation suggests repeated substring comparisons using substring operations (implicitly creating new string objects). In the worst-case scenario, where no matching prefixes/suffixes are found until a single character remains on either end, the comparisons may generate substrings of varying lengths, potentially up to the length of the original string, N. Thus, auxiliary space used for creating substrings can grow linearly with the input string's length. This leads to O(N) auxiliary space complexity.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 since an empty string decomposes into 0 chunks.
Single character string	Return 1 as a single character is a palindrome of itself.
String with two identical characters	Return 2 as the string can be decomposed into two identical chunks.
String with only one distinct character repeated multiple times (e.g., 'aaaa')	The algorithm should correctly decompose the string into the maximum possible chunks (e.g., 'a' + 'a' + 'a' + 'a' or 'aa' + 'aa').
Palindrome string (e.g., 'racecar')	Return 1 as the entire string is a single palindromic chunk.
Long string that exceeds memory constraints for substring comparisons (if not optimized)	Use efficient string comparison techniques (e.g., hashing, two-pointer approach) to avoid excessive memory usage.
String where no palindrome chunks can be formed (e.g., 'abcde')	The algorithm should correctly identify that no decomposition is possible and return 1 (entire string as a single chunk).
Very long input string to test for stack overflow with recursive solutions	Use iterative solution rather than recursion or implement tail-call optimization if language supports it.

Null or empty input string

How to Handle:

Return 0 since an empty string decomposes into 0 chunks.

Single character string

How to Handle:

Return 1 as a single character is a palindrome of itself.

String with two identical characters

How to Handle:

Return 2 as the string can be decomposed into two identical chunks.

String with only one distinct character repeated multiple times (e.g., 'aaaa')

How to Handle:

The algorithm should correctly decompose the string into the maximum possible chunks (e.g., 'a' + 'a' + 'a' + 'a' or 'aa' + 'aa').

Palindrome string (e.g., 'racecar')

How to Handle:

Return 1 as the entire string is a single palindromic chunk.

Long string that exceeds memory constraints for substring comparisons (if not optimized)

How to Handle:

Use efficient string comparison techniques (e.g., hashing, two-pointer approach) to avoid excessive memory usage.

String where no palindrome chunks can be formed (e.g., 'abcde')

How to Handle:

The algorithm should correctly identify that no decomposition is possible and return 1 (entire string as a single chunk).

Very long input string to test for stack overflow with recursive solutions

How to Handle:

Use iterative solution rather than recursion or implement tail-call optimization if language supports it.

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:

Can the input string be empty or null?
What is the maximum length of the input string?
If the string cannot be decomposed into palindrome chunks, what should I return?
Are the palindrome chunks required to be non-overlapping?
Can you provide a specific example of a string and its expected decomposition to confirm my understanding?

Brute Force Solution

Approach

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

Start by seeing if the entire string is a palindrome. If it is, we're done; the answer is one piece.
Next, try cutting off one character from the beginning and one character from the end. Check if these two single-character pieces are equal. If they are, that's two pieces, and we now have a smaller string in the middle to work with.
Then, try cutting off two characters from the beginning and two from the end. See if these two-character chunks are equal. If they are, that's two pieces, and we now have a smaller string in the middle.
Keep increasing the size of the chunks you cut off from both ends and check if they match. If they do, count them as two pieces and recursively apply the same process on the inner remaining string.
If no chunks match in a particular try, it means that the string cannot be further decomposed and we need to backtrack and try out other combinations by changing the length of the initial chunks.
Keep track of the maximum number of matching chunk pairs found through all the tried-out combinations and that would be our desired answer.

Code Implementation

def longest_chunked_palindrome_decomposition_brute_force(text):
    if not text:
        return 0

    if text == text[::-1]:
        return 1

    maximum_chunks = 1
    for chunk_length in range(1, len(text) // 2 + 1):
        # Check all possible chunk lengths
        if text[:chunk_length] == text[-chunk_length:]:

            # Recursively decompose remaining string
            remaining_text = text[chunk_length:-chunk_length]

            maximum_chunks = max(
                maximum_chunks,
                2 + longest_chunked_palindrome_decomposition_brute_force(remaining_text),
            )

    return maximum_chunks

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Compare the beginning of the string with the end of the string.
If the beginning and end match, consider this as one palindrome chunk, and remove those matched parts from both ends.
Repeat this process, each time shortening the string from both sides.
If the beginning and end *don't* match, shorten the end of the string by one character and try comparing again.
Continue shrinking the end until a match is found, or the shrinking part becomes empty.
Keep repeating this process, matching and removing chunks from both ends until the remaining part in the middle is either empty, or cannot be further divided.
If there's any remaining part in the middle that can't be divided, it counts as one last palindrome chunk.
The total number of chunks is the number of matched pairs plus one (if there's a remaining middle part).

Code Implementation

def longestDecomposition(text): 
    left_index = 0
    right_index = len(text) - 1
    chunk_count = 0

    while left_index <= right_index:
        sub_length = 1
        while left_index + sub_length - 1 < right_index - sub_length + 1:
            # Increment sub_length to find the largest possible match.
            sub_length += 1

        while sub_length > 0:
            left_substring = text[left_index:left_index + sub_length]
            right_substring = text[right_index - sub_length + 1:right_index + 1]

            # Greedily match substrings from the beginning and end.
            if left_substring == right_substring:
                chunk_count += 2
                left_index += sub_length
                right_index -= sub_length
                break
            else:
                sub_length -= 1

        # If no match is found, the remaining middle part is a chunk.
        if sub_length == 0:
            chunk_count += 1
            break

    return chunk_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 since an empty string decomposes into 0 chunks.
Single character string	Return 1 as a single character is a palindrome of itself.
String with two identical characters	Return 2 as the string can be decomposed into two identical chunks.
String with only one distinct character repeated multiple times (e.g., 'aaaa')	The algorithm should correctly decompose the string into the maximum possible chunks (e.g., 'a' + 'a' + 'a' + 'a' or 'aa' + 'aa').
Palindrome string (e.g., 'racecar')	Return 1 as the entire string is a single palindromic chunk.
Long string that exceeds memory constraints for substring comparisons (if not optimized)	Use efficient string comparison techniques (e.g., hashing, two-pointer approach) to avoid excessive memory usage.
String where no palindrome chunks can be formed (e.g., 'abcde')	The algorithm should correctly identify that no decomposition is possible and return 1 (entire string as a single chunk).
Very long input string to test for stack overflow with recursive solutions	Use iterative solution rather than recursion or implement tail-call optimization if language supports it.

Null or empty input string

How to Handle:

Return 0 since an empty string decomposes into 0 chunks.

Single character string

How to Handle:

Return 1 as a single character is a palindrome of itself.

String with two identical characters

How to Handle:

Return 2 as the string can be decomposed into two identical chunks.

String with only one distinct character repeated multiple times (e.g., 'aaaa')

How to Handle:

The algorithm should correctly decompose the string into the maximum possible chunks (e.g., 'a' + 'a' + 'a' + 'a' or 'aa' + 'aa').

Palindrome string (e.g., 'racecar')

How to Handle:

Return 1 as the entire string is a single palindromic chunk.

Long string that exceeds memory constraints for substring comparisons (if not optimized)

How to Handle:

Use efficient string comparison techniques (e.g., hashing, two-pointer approach) to avoid excessive memory usage.

String where no palindrome chunks can be formed (e.g., 'abcde')

How to Handle:

The algorithm should correctly identify that no decomposition is possible and return 1 (entire string as a single chunk).

Very long input string to test for stack overflow with recursive solutions

How to Handle:

Use iterative solution rather than recursion or implement tail-call optimization if language supports it.