131. Palindrome Partitioning - Detailed Explanation

Free Coding Questions Catalog
Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

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

A palindrome is a string that reads the same forward and backward.

Constraints:

  • The length of string s is between 1 and 16.
  • s consists of lowercase English letters only.

Example 1:

  • Input: s = "aab"
  • Output: [["a","a","b"], ["aa","b"]]
  • Explanation:
    • One valid partition is splitting into "a", "a", and "b", where each substring is a palindrome.
    • Another valid partition is splitting into "aa" and "b", where "aa" is a palindrome.

Example 2:

  • Input: s = "a"
  • Output: [["a"]]
  • Explanation:
    • The only possible partition is the string itself.

Example 3:

  • Input: s = "racecar"
  • Output: [["r", "a", "c", "e", "c", "a", "r"], ["r", "aceca", "r"], ["racecar"]]
  • Explanation:
    • There are multiple ways to partition "racecar" into palindromic substrings.

Hints Before the Solution

  • Hint 1: Think about how you can check if a substring is a palindrome in an efficient manner.
  • Hint 2: Consider using a backtracking approach to explore every possible partition and only keep the partitions where every substring is a palindrome.

Approaches

Approach 1: Brute Force (Generate All Partitions)

Explanation:

  • Idea:
    Generate all possible ways to partition the string into substrings, then check each partition to determine if every substring is a palindrome.
  • How It Works:
    • Enumerate every possible partition (there are (2^{(n-1)}) ways to partition a string of length (n)).
    • For each partition, verify if every substring is a palindrome.
  • Drawbacks:
    • This approach is conceptually simple but inefficient as it involves generating many invalid partitions.
  • Complexity:
    • Time: Exponential, O(2^n * n) in the worst-case.
    • Space: O(n) for recursion and partition storage.

Approach 2: Backtracking (Optimal Approach)

Explanation:

  • Idea:
    Use backtracking to explore possible partitions. At each step, choose a prefix that is a palindrome and recursively partition the remainder of the string.

  • How It Works:

    1. Start with an empty list for the current partition.
    2. Iterate through the string and for each index, check if the substring from the current start to that index is a palindrome.
    3. If it is, add it to the current partition and recursively process the remaining substring.
    4. When the entire string is partitioned, add the current partition to the result list.
  • Why It Works:
    This method only explores valid partitions by making sure each chosen substring is a palindrome before proceeding.

  • Complexity:

    • Time: Worst-case time is exponential O(2^n) since there can be a huge number of partitions.
    • Space: O(n) for recursion depth and temporary storage.

Python Code

Below is the Python implementation using a backtracking approach:

Python3
Python3

. . . .

Java Code

Below is the Java implementation using the backtracking approach.

Java
Java

. . . .

Complexity Analysis

  • Time Complexity:
    • Worst-Case: O(2^n * n), because in the worst-case scenario (e.g., when every substring is a palindrome, like in a string of identical characters), we explore nearly all possible partitionings.
  • Space Complexity:
    • O(n) for the recursion stack, plus additional space for storing the current partition, and the final results, which in the worst-case may also be exponential in number.

Step-by-Step Walkthrough & Visual Example

Consider the example s = "aab":

  1. Initial Call:
    Start with an empty partition and start = 0.

  2. First Level (start = 0):

    • Check substring "a" (indices 0 to 0): It is a palindrome.
      • Add "a" to the current partition → current partition becomes ["a"].
      • Recurse with start = 1.
    • Also, check substring "aa" (indices 0 to 1): It is a palindrome.
      • Add "aa" to the current partition → current partition becomes ["aa"].
      • Recurse with start = 2.
    • Substring "aab" (indices 0 to 2) is not a palindrome.
  3. Second Level (for partition ["a"], start = 1):

    • Check substring "a" (indices 1 to 1): It is a palindrome.
      • Add "a" to get ["a", "a"].
      • Recurse with start = 2.
    • Check substring "ab" (indices 1 to 2): Not a palindrome.
  4. Third Level (for partition ["a", "a"], start = 2):

    • Check substring "b" (indices 2 to 2): It is a palindrome.
      • Add "b" to get ["a", "a", "b"].
      • Since start becomes 3 (end of string), add this partition to the result.
  5. Backtracking:

    • Backtrack and try the partition starting with "aa" from the first level:
      • For partition ["aa"] (start = 2):
        • Check substring "b" (indices 2 to 2): It is a palindrome.
          • Add "b" → partition becomes ["aa", "b"].
          • Recurse with start = 3 and add this partition to the result.

Final Partitions:
The result will contain:

  • [["a", "a", "b"], ["aa", "b"]]

A visual tree of recursion would look like:

          ""
         /   \
       "a"   "aa"
       /       \
    "a"         "b"
    /             \
  "b"             (end)
   (end)

Common Mistakes, Edge Cases & Alternative Variations

Common Mistakes:

  • Incorrect Palindrome Check:
    Failing to correctly check if a substring is a palindrome (e.g., not handling even-length palindromes properly).
  • Inefficient Backtracking:
    Not backtracking correctly by forgetting to remove the last element, which can cause incorrect partitions.
  • Missing Base Case:
    Not handling the case when the entire string has been partitioned, leading to incomplete or incorrect results.

Edge Cases:

  • Single Character String:
    The string "a" should return [["a"]].
  • All Characters Same:
    For a string like "aaa", there are multiple valid partitions (e.g., ["a","a","a"], ["aa","a"], ["a","aa"], ["aaa"]).
  • Empty String:
    Although the constraints specify at least one character, always consider what your function should do if the input is empty.

Alternative Variations:

  • Minimum Palindrome Partitioning:
    Find the minimum number of cuts needed to partition the string such that every substring is a palindrome.

  • Longest Palindromic Substring:
    Given a string, find the longest substring which is a palindrome.

  • Palindrome Partitioning II:
    Variations where you may need to count the number of palindromic partitions or return the partition with specific constraints.

TAGS
leetcode
CONTRIBUTOR
Design Gurus Team
-

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
Related Courses
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the Coding Interview Patterns in Java, Python, JS, C++, C#, and Go. The most comprehensive course with 476 Lessons.
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
Grokking Data Structures & Algorithms for Coding Interviews
Unlock Coding Interview Success: Dive Deep into Data Structures and Algorithms.
Image
One-Stop Portal For Tech Interviews.
Copyright © 2025 Design Gurus, LLC. All rights reserved.
;