What happens if you not backtracking properly (forgetting to pop from path)?

Leads to incorrect partitions or duplicates in results Fix: Always pop the last added substring after recursive call returns

What happens if you not handling empty string or single character edge cases?

May cause errors or miss valid partitions Fix: Add base case for empty string and handle single characters as palindromes

Interview PrepbacktrackingmediumAmazonGoogleFacebook

Palindrome Partitioning

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

🎯

Palindrome Partitioning

mediumBACKTRACKINGAmazonGoogleFacebook

Imagine you want to split a secret message into palindromic chunks so that each chunk reads the same forwards and backwards, making it easier to encode or analyze.

💡 This problem requires exploring all possible ways to split a string into substrings that are palindromes. Beginners often struggle because it involves recursion with backtracking and pruning, which can be tricky to implement and understand. Think of it like trying every possible way to cut a string into pieces, but only keeping those pieces that read the same forwards and backwards.

📋

Problem Statement

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

1 ≤ s.length ≤ 16s consists of lowercase English letters only

💡

Example

Input"aab"

Outputaabaab

The string 'aab' can be partitioned into palindromes as ['a','a','b'] and ['aa','b'].

Empty string → [] (no partitions)
Single character string → [[char]] (only one partition)
String with all identical characters → multiple partitions with varying palindrome lengths
String with no palindromic substrings longer than 1 → partitions of single characters only

⚠️

Common Mistakes

Not backtracking properly (forgetting to pop from path)

Leads to incorrect partitions or duplicates in results

✅ Always pop the last added substring after recursive call returns

Checking palindrome inefficiently inside recursion repeatedly

Causes timeouts or slow performance

✅ Memoize palindrome checks or precompute palindrome table

Not handling empty string or single character edge cases

May cause errors or miss valid partitions

✅ Add base case for empty string and handle single characters as palindromes

Modifying shared path list without copying when adding to results

Results contain references to the same list, causing wrong outputs

✅ Add a copy of the current path (e.g., path[:], new ArrayList<>(path)) to results

Using substring indices incorrectly (off-by-one errors)

Incorrect substrings lead to wrong partitions or runtime errors

✅ Carefully use substring methods with correct start and end indices

🧠

Brute Force (Pure Recursion with Palindrome Check)

💡 This approach is the foundation: it tries every possible partition and checks if each substring is a palindrome. It helps understand the problem's exponential nature and the need for pruning. Imagine trying all ways to cut the string and only keeping those cuts where each piece is a palindrome.

Intuition

Try every possible substring starting from the current index. If the substring is a palindrome, recursively partition the remaining string. Collect all valid partitions.

Algorithm

Start from index 0 and try all substrings s[start:end].
Check if the substring is a palindrome.
If yes, add it to the current partition and recurse from end index.
When start reaches the end of the string, add the current partition to results.

💡 The challenge is to generate all partitions and prune invalid ones early by palindrome checks. This approach shows the brute force nature and why pruning is important.

</>

Code

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

    def backtrack(start, path):
        if start == len(s):
            result.append(path[:])
            return
        for end in range(start + 1, len(s) + 1):
            substr = s[start:end]
            if is_palindrome(substr):
                path.append(substr)
                backtrack(end, path)
                path.pop()

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

# Example usage
if __name__ == '__main__':
    print(partition("aab"))

Line Notes

def is_palindrome(sub):Helper function to check palindrome property of substring

return sub == sub[::-1]Simple palindrome check by reversing string

def backtrack(start, path):Recursive function exploring partitions from index start

if start == len(s):Base case: reached end of string, add current partition to results

for end in range(start + 1, len(s) + 1):Try all possible substring ends from start

substr = s[start:end]Extract substring to check

if is_palindrome(substr):Only proceed if substring is palindrome to prune search

path.append(substr)Choose this substring and add to current path

backtrack(end, path)Recurse to partition remaining string

path.pop()Backtrack to explore other partitions

result = []Stores all valid palindrome partitions

import java.util.*;

public class PalindromePartitioning {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(String s, int start, List<String> path, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            String substr = s.substring(start, end);
            if (isPalindrome(substr)) {
                path.add(substr);
                backtrack(s, end, path, result);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left++) != str.charAt(right--)) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        PalindromePartitioning sol = new PalindromePartitioning();
        System.out.println(sol.partition("aab"));
    }
}

Line Notes

public List<List<String>> partition(String s)Main function to start partitioning

backtrack(s, 0, new ArrayList<>(), result);Start recursion from index 0 with empty path

if (start == s.length())Base case: full partition found, add copy to result

for (int end = start + 1; end <= s.length(); end++)Try all substring ends from start

String substr = s.substring(start, end);Extract substring to check

if (isPalindrome(substr))Prune search by checking palindrome validity

path.add(substr);Choose substring and add to current partition path

backtrack(s, end, path, result);Recurse for remaining string

path.remove(path.size() - 1);Backtrack to explore other partitions

private boolean isPalindrome(String str)Helper to check palindrome by two pointers

while (left < right)Compare characters from both ends moving inward

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> path;
        backtrack(s, 0, path, result);
        return result;
    }

private:
    void backtrack(const string& s, int start, vector<string>& path, vector<vector<string>>& result) {
        if (start == s.size()) {
            result.push_back(path);
            return;
        }
        for (int end = start; end < s.size(); ++end) {
            if (isPalindrome(s, start, end)) {
                path.push_back(s.substr(start, end - start + 1));
                backtrack(s, end + 1, path, result);
                path.pop_back();
            }
        }
    }

    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left++] != s[right--]) return false;
        }
        return true;
    }
};

int main() {
    Solution sol;
    auto res = sol.partition("aab");
    for (auto& partition : res) {
        cout << "[";
        for (auto& str : partition) cout << str << ",";
        cout << "]\n";
    }
    return 0;
}

Line Notes

vector<vector<string>> partition(string s)Main function to initiate backtracking

backtrack(s, 0, path, result);Start recursion from index 0 with empty path

if (start == s.size())Base case: full partition found, add to result

for (int end = start; end < s.size(); ++end)Try all substring ends from start

if (isPalindrome(s, start, end))Check palindrome to prune invalid partitions

path.push_back(s.substr(start, end - start + 1));Add current palindrome substring to path

backtrack(s, end + 1, path, result);Recurse for remaining substring

path.pop_back();Backtrack to try other partitions

bool isPalindrome(const string& s, int left, int right)Helper to check palindrome using two pointers

while (left < right)Compare characters inward from both ends

function partition(s) {
    const result = [];
    function isPalindrome(sub) {
        let left = 0, right = sub.length - 1;
        while (left < right) {
            if (sub[left++] !== sub[right--]) return false;
        }
        return true;
    }

    function backtrack(start, path) {
        if (start === s.length) {
            result.push([...path]);
            return;
        }
        for (let end = start + 1; end <= s.length; end++) {
            const substr = s.slice(start, end);
            if (isPalindrome(substr)) {
                path.push(substr);
                backtrack(end, path);
                path.pop();
            }
        }
    }

    backtrack(0, []);
    return result;
}

// Example usage
console.log(partition("aab"));

Line Notes

function isPalindrome(sub)Helper function to check if substring is palindrome

let left = 0, right = sub.length - 1;Initialize pointers for palindrome check

while (left < right)Two-pointer palindrome check moving inward

if (sub[left++] !== sub[right--]) return false;Return false immediately if mismatch found

function backtrack(start, path)Recursive function to explore partitions from start

if (start === s.length)Base case: reached end, add current partition copy to result

for (let end = start + 1; end <= s.length; end++)Try all substring ends from start

const substr = s.slice(start, end);Extract substring to check

if (isPalindrome(substr))Prune search by palindrome validation

path.push(substr)Add substring to current partition path

backtrack(end, path)Recurse for remaining string

path.pop()Backtrack to try other partitions

result.push([...path])Add a copy of current partition to results

⏱

Complexity

TimeO(N * 2^N)

SpaceO(N)

There are up to 2^(N-1) ways to partition a string of length N. Each partition requires palindrome checks which take O(N) time, leading to O(N * 2^N) time complexity.

💡 For n=10, this means roughly 10 * 2^10 = 10,240 operations, which is feasible, but for n=16 it grows exponentially and becomes slow.

Interview Verdict: Use only to introduce - too slow for large inputs

This approach is simple but inefficient; it helps understand the problem but is impractical for large strings due to exponential time.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(N * 2^N)`	`O(N)`	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Palindrome Memoization	`O(N * 2^N)`	`O(N^2)`	Yes (deep recursion)	Yes	Code this approach in interviews
3. Backtracking with Dynamic Palindrome Check	`O(N * 2^N)`	`O(N)`	Yes (deep recursion)	Yes	Mention as memory-optimized alternative

Practice

(1/5)

1. You need to count all distinct ways to place n queens on an nxn chessboard so that no two queens threaten each other. Which algorithmic approach guarantees finding all valid solutions efficiently by exploring partial placements and pruning invalid ones early?

easy

A. Backtracking that tries all column placements per row and abandons invalid partial boards

B. Greedy algorithm that places queens row by row choosing the first safe column

C. Dynamic programming that stores counts of valid queen placements per row without conflict checks

D. Breadth-first search enumerating all board states level by level

4. Examine the following snippet from an optimized Sudoku solver. Which line contains a subtle bug that can cause incorrect solutions or failure to backtrack properly?

def backtrack():
    if not empties:
        return True
    empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
    r, c = empties[0]
    for ch in get_candidates(r, c):
        board[r][c] = ch
        rows[r].add(ch)
        cols[c].add(ch)
        boxes[(r//3)*3 + c//3].add(ch)
        empties.pop(0)
        if backtrack():
            return True
        # Undo changes
        board[r][c] = '.'
        rows[r].remove(ch)
        cols[c].remove(ch)
        boxes[(r//3)*3 + c//3].remove(ch)
        empties.insert(0, (r, c))
    return False

medium

A. Line that pops the first empty cell from empties

B. Line that sorts empties by candidate count

C. Line that adds ch to rows[r]

D. Line that resets board[r][c] to '.' after backtracking

Start learning this pattern below

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand problem constraints

Step 2: Identify suitable algorithm

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Identify the approach that uses factorial number system

Final Answer:

Quick Check:

Solution

Step 1: Identify the branching factor per row

Step 2: Understand factorial growth

Final Answer:

Quick Check:

Solution

Step 1: Identify mutation of empties list

Step 2: Consequence of missing restoration

Final Answer:

Quick Check:

Solution

Step 1: Understand new constraint

Step 2: Modify algorithm accordingly

Step 3: Evaluate other options

Final Answer:

Quick Check: