Palindrome Partitioning

TIP103 Unit 8 Session 2 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-35 mins
• 🛠️ Topics: Backtracking, Recursion, Strings, Palindromes

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What counts as a valid partition?

  • A split of s into consecutive, non-overlapping substrings that concatenate back to s, where every substring is a palindrome.

• Do we return one partition or all of them?

  • All possible palindrome partitionings, as a list of lists of strings, in any order.

• Is a single character a palindrome?

  • Yes. Every one-character string reads the same forwards and backwards, so splitting s into individual characters is always a valid partition.

HAPPY CASE
Input: s = "aab"
Output: [['a', 'a', 'b'], ['aa', 'b']]
Explanation: "aab" can be split as 'a' + 'a' + 'b' (all single characters are palindromes) or as 'aa' + 'b' ('aa' is a palindrome). 'aab' itself and 'ab' are not palindromes, so no other partition works.

EDGE CASE
Input: s = "a"
Output: [['a']]
Explanation: A single character has exactly one partition: itself.

Input: s = "ab"
Output: [['a', 'b']]
Explanation: 'ab' is not a palindrome, so the only valid partition splits the string into single characters.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Generate All Combinations/Partitions problems, we can consider the following approaches:

• Backtracking (DFS): At each position, try every prefix that is a palindrome, recurse on the rest of the string, and undo the choice before trying the next prefix. This is the standard pattern whenever a problem asks for all valid answers rather than a count or a best answer.
• Dynamic Programming (optimization): A DP table of "is s[i:j] a palindrome?" can be precomputed to avoid re-checking substrings, but the enumeration itself still requires backtracking.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Build partitions one piece at a time. From a starting index, cut off every possible prefix; if the prefix is a palindrome, add it to the current partition and recurse on the remainder of the string. When the starting index reaches the end of the string, the current partition is complete — record a copy of it. After each recursive call, pop the piece off (backtrack) so the next prefix length can be tried.

1) Initialize an empty `result` list and an empty `current` partition.
2) Define a helper `backtrack(start)`:
   a) Base case: if `start` equals the length of `s`, append a copy of `current` to `result` and return.
   b) For each `end` from `start + 1` to `len(s)`:
      i)   Let `piece = s[start:end]`.
      ii)  If `piece` is a palindrome (reads the same reversed):
           - Append `piece` to `current`.
           - Recurse with `backtrack(end)`.
           - Pop `piece` off `current` to undo the choice.
3) Call `backtrack(0)` and return `result`.

⚠️ Common Mistakes

• Appending current itself instead of a copy (current[:]), so every recorded partition mutates into the same empty list by the end.
• Off-by-one on the slice: forgetting that range(start + 1, len(s) + 1) must reach len(s) so the final character can end a piece.
• Forgetting to pop after the recursive call, which corrupts the partition for later prefix choices.
• Recursing on non-palindrome prefixes and trying to filter at the end, which explodes the search space instead of pruning early.

4: I-mplement

Implement the code to solve the algorithm.

def partition(s):
    def is_palindrome(sub):
        return sub == sub[::-1]

    def backtrack(start, current):
        # Base case: every character is placed in a palindrome piece
        if start == len(s):
            result.append(current[:])  # record a copy of the finished partition
            return
        # Try every possible end index for the next piece
        for end in range(start + 1, len(s) + 1):
            piece = s[start:end]
            if is_palindrome(piece):
                current.append(piece)    # choose
                backtrack(end, current)  # explore the rest of the string
                current.pop()            # un-choose (backtrack)

    result = []
    backtrack(0, [])
    return result

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: s = "aab"

  • backtrack(0): piece 'a' (palindrome) → recurse.
    • backtrack(1): piece 'a' (palindrome) → recurse.
      • backtrack(2): piece 'b' (palindrome) → recurse.
        • backtrack(3): start == len(s), record ['a', 'a', 'b'].
      • Piece 'ab' is not a palindrome — skip.
    • Piece 'aa' from index 0 (palindrome) → recurse.
      • backtrack(2): piece 'b' (palindrome) → recurse → record ['aa', 'b'].
  • Piece 'aab' is not a palindrome — skip.
  • Output: 'a', 'a', 'b'], ['aa', 'b'

• Input: s = "a"

  • backtrack(0) chooses 'a', then backtrack(1) records ['a'].
  • Output: 'a'

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the length of the string s.

• Time Complexity: O(N * 2^N) because there are up to 2^(N-1) ways to place cuts in the string, and for each partition explored we do O(N) work checking palindromes and copying the finished partition.
• Space Complexity: O(N) auxiliary space for the recursion stack and the current partition (excluding the output list, which itself can hold O(N * 2^N) characters in the worst case, e.g. s = "aaaa...").