Problem Statement in English

You’re given a string s. Your task is to partition the string into substrings such that each substring is a palindrome.

Approach

The way I like to think about this is first build the portion that will generate all possible substrings of a string.

Then, we can filter out the substrings that are not palindromes.

If you need to work on your backtracking, I’d suggest checking out this problem.

Solution in Python


class Solution:

    def partition(self, s: str) -> List[List[str]]:
        # we store all the partitions here
        ans = []

        # check if a string is a palindrome
        # this uses a 2 pointer technique to ensure O(1) space
        def isPalindrome(s: str) -> bool:
            l, r = 0, len(s) - 1

            while l <= r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1

            return True

        @cache
        def recursiveCall(buffer: tuple[str], index: int):
            
            # check if `index` is within bounds
            if index < len(s):
                # append to end of last string if one exists
                if len(buffer) > 0:
                    yes = list(buffer)
                    # concat the current character with the last string in the list
                    yes[-1] = yes[-1] + s[index]

                    # make a recursive call to continue 
                    # building on this possibility
                    recursiveCall(tuple(yes), index + 1)  # type: ignore

                # or add to list as new string
                no = list(buffer)
                # we don't add the current character to the last string
                no.append(s[index])

                # make a recursive call to continue 
                # building on this possibility
                recursiveCall(tuple(no), index + 1)  # type: ignore

            # if the index is out of bounds
            else:
                # this is one possible way to partition the string
                ans.append(buffer)

        # this is the initial call to the recursive function
        recursiveCall((), 0)  # type:ignore

        # stores the final answer
        finalAns = []

        # check if the partition combination is valid
        for option in ans:
            # set the flag to `True`
            flag = True
            # check if each substring is a palindrome
            for substring in option:
                # if it is not a palindrome
                if not isPalindrome(substring):
                    # set the flag to `False`
                    flag = False
                    break

            # check the flag
            if flag:
                # add to the final answer
                finalAns.append(option)

        # return the final answer
        return finalAns

Complexity

  • Time: $O(n*2^n)$
    Since we iterate over $n$ characters and generate $2^n$ possible partitions for each.

  • Space: $O(n*2^n)$
    This is because our final answer list contains $2^n$ possible answers, with each answer containing $n$ elements at most. Hence $n \times 2^n$.

And we are done.