Palindrome Partitioning

🎯

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

1. Start from index 0 and try all substrings s[start:end].
2. Check if the substring is a palindrome.
3. If yes, add it to the current partition and recurse from end index.
4. 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.

🧠

Backtracking with Palindrome Memoization

💡 This approach improves brute force by caching palindrome checks to avoid repeated work, making the solution faster and more practical. Think of it as having a cheat sheet that tells you instantly if any substring is a palindrome, so you don't waste time checking it multiple times.

Intuition

Store results of palindrome checks in a 2D table so that each substring is checked only once. Use this table during backtracking to prune invalid partitions quickly.

Algorithm

1. Precompute a 2D boolean table is_palindrome[i][j] indicating if s[i:j] is palindrome.
2. Use backtracking to generate partitions, but check palindrome validity from the table in O(1).
3. Add valid palindrome substrings to current path and recurse.
4. Add completed partitions to results when end of string is reached.

💡 Precomputing palindrome info upfront reduces repeated substring checks during recursion, improving efficiency.

</>

Code

def partition(s):
    n = len(s)
    is_palindrome = [[False]*n for _ in range(n)]

    for i in range(n-1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 3 or is_palindrome[i+1][j-1]):
                is_palindrome[i][j] = True

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

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

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

Line Notes

n = len(s)Store length of string for convenience

is_palindrome = [[False]*n for _ in range(n)]Initialize 2D table to store palindrome info

for i in range(n-1, -1, -1)Fill table bottom-up to use previously computed results

for j in range(i, n)Check all substrings starting at i

if s[i] == s[j] and (j - i < 3 or is_palindrome[i+1][j-1])Check palindrome condition using smaller substring info

is_palindrome[i][j] = TrueMark substring as palindrome

def backtrack(start, path)Backtracking function uses precomputed palindrome table

if start == nBase case: reached end, add current partition to results

for end in range(start, n)Try all substring ends from start

if is_palindrome[start][end]Check palindrome in O(1) from table instead of recomputing

path.append(s[start:end+1])Add valid palindrome substring to current path

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

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) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 3 || isPalindrome[i + 1][j - 1])) {
                    isPalindrome[i][j] = true;
                }
            }
        }

        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result, isPalindrome);
        return result;
    }

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

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

Line Notes

int n = s.length()Store length of string for convenience

boolean[][] isPalindrome = new boolean[n][n];2D array to store palindrome info for substrings

for (int i = n - 1; i >= 0; i--)Fill palindrome table bottom-up for reuse

for (int j = i; j < n; j++)Check all substrings starting at i

if (s.charAt(i) == s.charAt(j) && (j - i < 3 || isPalindrome[i + 1][j - 1]))Palindrome condition using smaller substring info

isPalindrome[i][j] = trueMark substring as palindrome

backtrack(s, 0, new ArrayList<>(), result, isPalindrome);Start backtracking with precomputed palindrome table

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

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

if (isPalindrome[start][end])Check palindrome in O(1) during recursion

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

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

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

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

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j] && (j - i < 3 || isPalindrome[i + 1][j - 1])) {
                    isPalindrome[i][j] = true;
                }
            }
        }

        vector<vector<string>> result;
        vector<string> path;
        backtrack(s, 0, path, result, isPalindrome);
        return result;
    }

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

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

int n = s.size()Store length of string for convenience

vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));2D vector to store palindrome info

for (int i = n - 1; i >= 0; --i)Fill palindrome table bottom-up for reuse

for (int j = i; j < n; ++j)Check all substrings starting at i

if (s[i] == s[j] && (j - i < 3 || isPalindrome[i + 1][j - 1]))Palindrome condition using smaller substring info

isPalindrome[i][j] = trueMark substring as palindrome

backtrack(s, 0, path, result, isPalindrome);Start backtracking with precomputed palindrome table

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[start][end])Check palindrome in O(1) during recursion

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

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

path.pop_back();Backtrack to explore other partitions

function partition(s) {
    const n = s.length;
    const isPalindrome = Array.from({ length: n }, () => Array(n).fill(false));

    for (let i = n - 1; i >= 0; i--) {
        for (let j = i; j < n; j++) {
            if (s[i] === s[j] && (j - i < 3 || isPalindrome[i + 1][j - 1])) {
                isPalindrome[i][j] = true;
            }
        }
    }

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

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

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

Line Notes

const n = s.lengthStore length of string for convenience

const isPalindrome = Array.from({ length: n }, () => Array(n).fill(false));Initialize 2D array for palindrome info

for (let i = n - 1; i >= 0; i--)Fill palindrome table bottom-up for reuse

for (let j = i; j < n; j++)Check all substrings starting at i

if (s[i] === s[j] && (j - i < 3 || isPalindrome[i + 1][j - 1]))Palindrome condition using smaller substring info

isPalindrome[i][j] = trueMark substring as palindrome

function backtrack(start, path)Backtracking function uses precomputed palindrome table

if (start === n)Base case: reached end, add current partition to results

for (let end = start; end < n; end++)Try all substring ends from start

if (isPalindrome[start][end])Check palindrome in O(1) during recursion

path.push(s.slice(start, end + 1))Add palindrome substring to current path

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

path.pop()Backtrack to explore other partitions

⏱

Complexity

TimeO(N * 2^N)

SpaceO(N^2)

Precomputing palindrome table takes O(N^2). Backtracking still explores up to 2^N partitions but palindrome checks are O(1), improving efficiency.

💡 For n=16, this approach is much faster than brute force because palindrome checks are instant, making it practical for interview constraints.

Interview Verdict: Accepted - practical and efficient for interview use

This approach balances clarity and efficiency, making it a strong candidate for coding in interviews.

🧠

Backtracking with Dynamic Palindrome Check (Expand Around Center)

💡 Instead of precomputing all palindromes, this approach checks palindrome substrings on the fly by expanding around centers, reducing memory usage. It trades some speed for lower memory, which can be useful in memory-constrained environments.

Intuition

At each recursion step, expand around the current substring to check palindrome validity without a large DP table, then recurse if valid.

Algorithm

1. At each recursion, try all substrings starting at current index.
2. Check palindrome by expanding around substring boundaries.
3. If palindrome, add substring to path and recurse.
4. Add completed partitions to results when end of string is reached.

💡 This approach trades some speed for lower memory by avoiding a large DP table, still pruning invalid partitions early.

</>

Code

def partition(s):
    def is_palindrome(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

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

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

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

Line Notes

def is_palindrome(left, right):Check palindrome by expanding around substring boundaries

while left < right:Compare characters inward from both ends

if s[left] != s[right]:Return False immediately if mismatch found

left += 1Move left pointer inward

right -= 1Move right pointer inward

return TrueSubstring is palindrome if no mismatches found

def backtrack(start, path):Recursive function to explore partitions

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

for end in range(start, len(s))Try all substring ends from start

if is_palindrome(start, end)Check palindrome dynamically before recursion

path.append(s[start:end+1])Add palindrome substring to current path

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

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; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                path.add(s.substring(start, end + 1));
                backtrack(s, end + 1, path, result);
                path.remove(path.size() - 1);
            }
        }
    }

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

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

Line Notes

private void backtrack(String s, int start, List<String> path, List<List<String>> result)Recursive function exploring partitions

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

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

if (isPalindrome(s, start, end))Check palindrome dynamically before recursion

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

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

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

private boolean isPalindrome(String s, int left, int right)Check palindrome by expanding around substring boundaries

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

if (s.charAt(left++) != s.charAt(right--)) return false;Return false immediately if mismatch

#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

void backtrack(const string& s, int start, vector<string>& path, vector<vector<string>>& result)Recursive function exploring partitions

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 dynamically before recursion

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

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

path.pop_back();Backtrack to explore other partitions

bool isPalindrome(const string& s, int left, int right)Check palindrome by expanding around substring boundaries

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

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

function partition(s) {
    const result = [];

    function isPalindrome(left, right) {
        while (left < right) {
            if (s[left] !== s[right]) return false;
            left++;
            right--;
        }
        return true;
    }

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

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

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

Line Notes

function isPalindrome(left, right)Check palindrome by expanding around substring boundaries

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

if (s[left] !== s[right]) return false;Return false immediately if mismatch

left++Move left pointer inward

right--Move right pointer inward

return trueSubstring is palindrome if no mismatches found

function backtrack(start, path)Recursive function exploring partitions

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

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

if (isPalindrome(start, end))Check palindrome dynamically before recursion

path.push(s.slice(start, end + 1))Add palindrome substring to current path

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

path.pop()Backtrack to explore other partitions

⏱

Complexity

TimeO(N * 2^N)

SpaceO(N)

Palindrome checks take O(N) each, and there are up to 2^N partitions, so total time is O(N * 2^N). Space is O(N) for recursion stack and path.

💡 This approach uses less memory than precomputing all palindromes but may be slower for large inputs due to repeated palindrome checks.

Interview Verdict: Accepted - good memory tradeoff, slightly slower than memoized palindrome

This approach is useful when memory is limited but still efficient enough for typical interview constraints.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 (Backtracking with Palindrome Memoization) is recommended for most interviews due to its balance of clarity and efficiency.

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

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, optimize palindrome checks, and finally discuss tradeoffs.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force recursive approach with palindrome checks.Step 3: Explain how to optimize palindrome checks with memoization.Step 4: Optionally mention dynamic palindrome checking to save space.Step 5: Code the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of backtracking, pruning, palindrome checking, and optimization techniques.

Common Follow-ups

• How to find the minimum cuts needed for palindrome partitioning? → Use DP to find minimum cuts.
• Can you optimize palindrome checking further? → Use Manacher's algorithm or expand around center.

💡 These follow-ups test your ability to extend the problem and optimize further, common in FAANG interviews.

🔍

Pattern Recognition

When to Use

1) Asked to partition string into substrings; 2) Each substring must satisfy a property (palindrome); 3) Need all possible partitions; 4) Problem hints at recursion or backtracking.

Signature Phrases

'partition s such that every substring is a palindrome''return all possible palindrome partitioning'

NOT This Pattern When

Problems asking only for count of partitions or minimum cuts without generating all partitions

Similar Problems

Palindrome Partitioning II - focuses on minimum cuts instead of all partitionsRestore IP Addresses - partitions string into valid IP segmentsWord Break II - partitions string into dictionary words

Practice

1. Consider the following snippet from an optimized Sudoku solver using backtracking with heuristics. Given the board below, what is the length of candidates for the first empty cell chosen after sorting empties by candidate count? Board: [['5', '3', '.', '.', '7', '.', '.', '.', '.'], ['6', '.', '.', '1', '9', '5', '.', '.', '.'], ['.', '9', '8', '.', '.', '.', '.', '6', '.'], ['8', '.', '.', '.', '6', '.', '.', '.', '3'], ['4', '.', '.', '8', '.', '3', '.', '.', '1'], ['7', '.', '.', '.', '2', '.', '.', '.', '6'], ['.', '6', '.', '.', '.', '.', '2', '8', '.'], ['.', '.', '.', '4', '1', '9', '.', '.', '5'], ['.', '.', '.', '.', '8', '.', '.', '7', '9']] Code snippet:

def get_candidates(r, c):
    b = (r//3)*3 + c//3
    return [ch for ch in '123456789' if ch not in rows[r] and ch not in cols[c] and ch not in boxes[b]]

empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
first_empty = empties[0]
candidates_len = len(get_candidates(first_empty[0], first_empty[1]))

What is the value of candidates_len?

easy

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Identify first empty cell after sorting

   Check empties and compute candidates for each; the cell with fewest candidates is chosen first.

2. Step 2: Calculate candidates for first empty cell (0,2)

   Row 0 has {'5','3','7'}, column 2 has {'8'}, box 0 has {'5','3','6','9','8'}. Candidates are digits not in any of these sets: '1','2','4'. So length is 3.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Counting candidates for (0,2) yields 3 [OK]

Hint: Count candidates by excluding row, column, box digits [OK]

Common Mistakes:

• Forgetting box constraints
• Miscounting candidates for first empty cell

2. 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

Solution

1. Step 1: Identify mutation of empties list

   The line popping empties[0] removes the cell but is never restored on backtrack failure.

2. Step 2: Consequence of missing restoration

   Without re-adding the cell to empties after failed recursion, future calls miss this cell, causing incorrect state and solutions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking requires undoing all changes including empties list [OK]

Hint: Backtracking must undo all state changes, including empties list [OK]

Common Mistakes:

• Forgetting to restore empties after pop
• Assuming board reset is sufficient

3. Suppose you want to find the lexicographically next permutation of an array where elements can be repeated and reused multiple times (infinite supply). Which modification to the standard next permutation algorithm is necessary?

hard

A. No modification needed; the standard next permutation algorithm works as is.

B. Modify the algorithm to generate all permutations with repetition and pick the next one, since in-place approach fails.

C. Adjust the pivot search to consider repeated elements and skip duplicates to avoid redundant swaps.

D. Use a backtracking approach that allows repeated elements and generates permutations with repetition.

Solution

1. Step 1: Understand the problem variant

   Allowing repeated use of elements means permutations with repetition, which standard next permutation does not handle as it assumes fixed elements.

2. Step 2: Identify correct approach

   Backtracking that generates permutations with repetition is required, as in-place next permutation only rearranges existing elements without reuse.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Standard next permutation assumes fixed elements; repeated reuse requires backtracking [OK]

Hint: Next permutation assumes fixed elements; reuse needs backtracking [OK]

Common Mistakes:

• Thinking standard algorithm handles reuse
• Trying to modify pivot logic only

4. If the problem changes so that numbers can be reused multiple times in the permutation (i.e., repetition allowed), which modification to the algorithm is correct?

hard

A. Use a greedy approach to pick the smallest available number at each step until length n is reached.

B. Use the same factorial-based approach but do not remove numbers from the list after selection.

C. Modify factorial computations to account for repeated elements and use a multiset permutation formula.

D. Generate all permutations with backtracking and stop when the k-th is found, since factorial indexing no longer applies.

Solution

1. Step 1: Understand repetition impact

   Allowing reuse breaks the factorial number system assumption because permutations count changes drastically.

2. Step 2: Identify correct approach

   Backtracking with early stop can generate permutations with repetition and find the k-th one, as direct factorial indexing is invalid.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Factorial indexing fails with repetition; backtracking is correct fallback [OK]

Hint: Factorial indexing requires unique elements; repetition breaks it [OK]

Common Mistakes:

• Trying to reuse factorial indexing without adjustment
• Ignoring repetition changes permutation count
• Assuming greedy works for k-th permutation with repetition

5. Suppose the problem is modified so that parentheses can be reused multiple times (e.g., you can insert removed parentheses back anywhere). Which of the following algorithmic changes correctly adapts the BFS approach to handle this variant?

hard

A. Switch to backtracking with memoization to explore insertions and removals explicitly, pruning invalid states

B. Use BFS as is, since it already explores all possible removals and insertions implicitly

C. Use a greedy approach to insert parentheses at earliest invalid positions without BFS or backtracking

D. Modify BFS to allow adding parentheses back by generating new states with insertions at every position

Solution

1. Step 1: Understand reuse of parentheses

   Allowing reuse means we can insert parentheses anywhere, greatly increasing state space and complexity.

2. Step 2: Analyze BFS suitability

   Standard BFS only removes characters; it does not handle insertions, so it cannot explore all states correctly.

3. Step 3: Identify correct approach

   Backtracking with memoization can explicitly explore insertions and removals, pruning invalid states to handle reuse properly.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with memoization handles insertions and pruning [OK]

Hint: Reuse requires explicit insertion exploration, not just removal BFS [OK]

Common Mistakes:

• Assuming BFS handles insertions
• Using greedy for complex insertions
• Modifying BFS without pruning leads to explosion