Course4all
Join us on telegram
Home/dsa/Backtracking/Palindrome Partitioning

Palindrome Partitioning

Master this topic with zero to advance depth.

Palindrome Partitioning

Partitioning Strategy

A string can be partitioned in many ways. For Palindrome Partitioning, we only care about partitions where every substring is a palindrome.

The Decision Tree

At each step, we pick a substring s[start:end]. If it's a palindrome, we recurse on the remaining string s[end:].

Optimization with DP

Checking if a substring is a palindrome repeatedly is O(N)O(N). We can precompute a 2D boolean array isPalindrome[i][j] using Dynamic Programming in O(N2)O(N^2) to make each check O(1)O(1).

Partition a string into all possible palindromic substrings. Includes visual cut-tree.

Medium

Examples

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Approach 1

Level I: Standard Backtracking

Intuition

Try all possible prefixes. If a prefix is a palindrome, recurse on the suffix.

Iterate through the string. At each position, try taking a substring from the start to the current position. If it's a palindrome, add it to the path and recurse.

⏱ O(N * 2^N)💾 O(N)

Detailed Dry Run

Dry Run: s="aab" | Start | Substr | Is Pal? | Path | Action | | :---- | :----- | :------ | :--- | :--- | | 0 | "a" | YES | ["a"] | DFS(1) | | 1 | "a" | YES | ["a","a"] | DFS(2) | | 2 | "b" | YES | ["a","a","b"]| RES!! | | 0 | "aa" | YES | ["aa"] | DFS(2) | | 2 | "b" | YES | ["aa","b"] | RES!! |
java
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtrack(0, s, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int start, String s, List<String> current, List<List<String>> res) {
        if (start == s.length()) {
            res.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome(s, start, i)) {
                current.add(s.substring(start, i + 1));
                backtrack(i + 1, s, current, res);
                current.remove(current.size() - 1);
            }
        }
    }
    private boolean isPalindrome(String s, int low, int high) {
        while (low < high) {
            if (s.charAt(low++) != s.charAt(high--)) return false;
        }
        return true;
    }
}
Approach 2

Level II: Backtracking with DP Precomputation

Intuition

Avoid repetitive palindrome checks by precomputing all possible palindromes in the string.

Create a 2D boolean array dp[i][j] where dp[i][j] is true if s[i:j+1] is a palindrome. Use the recurrence: dp[i][j] = (s[i] == s[j] && (j - i <= 2 || dp[i+1][j-1])).

⏱ O(2^N)💾 O(N^2)

Detailed Dry Run

s="aab" dp[0][0]=T, dp[1][1]=T, dp[2][2]=T dp[0][1] = (s[0]==s[1]) = T dp[1][2] = (s[1]==s[2]) = F dp[0][2] = (s[0]==s[2] && dp[1][1]) = F

java
class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] dp = 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 <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                }
            }
        }
        List<List<String>> res = new ArrayList<>();
        backtrack(0, s, dp, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int start, String s, boolean[][] dp, List<String> current, List<List<String>> res) {
        if (start == s.length()) {
            res.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (dp[start][i]) {
                current.add(s.substring(start, i + 1));
                backtrack(i + 1, s, dp, current, res);
                current.remove(current.size() - 1);
            }
        }
    }
}
← Previous QuestionSudoku Solver
Next Question →N-Queens II