We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Palindrome Partitioning

Number: 131

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Meta, Microsoft, Bloomberg, Adobe, Apple, Uber, Yahoo, Infosys

Problem Description

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s.

Key Insights

  • Use backtracking to explore all possible ways to partition the string.
  • At each step, check whether the current substring is a palindrome.
  • If it is, include that substring in the current partition and recursively partition the rest of the string.
  • The limit on the string length (at most 16 characters) allows an exponential backtracking approach.
  • Optimizations like caching palindrome checks can be used, though the simple approach is typically sufficient.

Space and Time Complexity

Time Complexity: O(n * 2^n) in the worst case, due to exploring all possible partitions and checking palindromes. Space Complexity: O(n) for recursion stack and temporary storage for current partition.

Solution

The solution uses the backtracking algorithm:

  1. Define a helper function that will recursively try to partition the string.
  2. For each possible split, check if the substring is a palindrome.
  3. If it is, add the substring to the current partition list and recursively call the helper on the remaining substring.
  4. When the end of the string is reached, add the current partition list to the final result.
  5. Backtrack by removing the last added substring and try the next possible partition. This method systematically explores every possible palindrome partitioning of the string.

Code Solutions

def partition(s):
    # Helper function to check if a given substring is a palindrome
    def is_palindrome(sub):
        return sub == sub[::-1]

    result = []  # final list to store all possible partitions
    
    # backtracking helper function: current_index points to the starting index of the current search,
    # current_partition stores the partition done so far.
    def backtrack(current_index, current_partition):
        # if we reached the end of the string, add the current_partition to the result list
        if current_index == len(s):
            result.append(list(current_partition))
            return
        # try all possible substrings starting from current_index
        for i in range(current_index, len(s)):
            substring = s[current_index:i+1]  # current substring
            # if the substring is a palindrome, add it to current_partition
            if is_palindrome(substring):
                current_partition.append(substring)
                backtrack(i+1, current_partition)
                # backtrack: remove the last added substring
                current_partition.pop()

    backtrack(0, [])
    return result

# Example usage:
print(partition("aab"))
← Back to All Questions