Palindrome Partitioning

Problem Description

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

Examples

Constraints

• 1 ≤ s.length ≤ 16
• s contains only lowercase English letters

Cut at Every Valid Split Point

At each position in the string, you’re asking: where do I make the next cut? For every possible cut, check if the substring from the current start to that cut is a palindrome. If it is, take that substring, add it to the current partition, and recurse on the remainder. If not, skip that cut point.

Single characters are always palindromes, so every string has at least one valid partitioning (all individual characters).

Solution: Backtracking with Palindrome Check

import java.util.*;

class Solution {
    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> current, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int end = start + 1; end <= s.length(); end++) {
            String sub = s.substring(start, end);
            if (isPalindrome(sub)) {
                current.add(sub);
                backtrack(s, end, current, result);
                current.remove(current.size() - 1);
            }
        }
    }

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

class Solution:
    def partition(self, s: str) -> list[list[str]]:
        result = []

        def is_palindrome(sub: str) -> bool:
            return sub == sub[::-1]

        def backtrack(start: int, current: list[str]):
            if start == len(s):
                result.append(current[:])
                return

            for end in range(start + 1, len(s) + 1):
                sub = s[start:end]
                if is_palindrome(sub):
                    current.append(sub)
                    backtrack(end, current)
                    current.pop()

        backtrack(0, [])
        return result

#include <vector>
#include <string>

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

private:
    bool isPalindrome(const std::string& s, int l, int r) {
        while (l < r) {
            if (s[l++] != s[r--]) return false;
        }
        return true;
    }

    void backtrack(const std::string& s, int start,
                   std::vector<std::string>& current,
                   std::vector<std::vector<std::string>>& result) {
        if (start == (int)s.size()) {
            result.push_back(current);
            return;
        }

        for (int end = start + 1; end <= (int)s.size(); end++) {
            if (isPalindrome(s, start, end - 1)) {
                current.push_back(s.substr(start, end - start));
                backtrack(s, end, current, result);
                current.pop_back();
            }
        }
    }
};

Complexity Analysis:

• Time Complexity: O(n * 2^n). There are 2^(n-1) ways to partition a string of length n (each of the n-1 gaps is a potential cut point). Checking each substring for palindrome costs up to O(n).
• Space Complexity: O(n) recursion depth.

Where it breaks: the palindrome check inside the loop runs repeatedly on the same substrings. For n = 16, this is acceptable given the constraints. For larger strings, precompute a 2D DP table dp[i][j] = true if s[i..j] is a palindrome to bring palindrome checks to O(1).

Common Mistakes

• Using end = start instead of end = start + 1. A zero-length substring is not a valid partition component. Start end at start + 1 to guarantee at least one character.
• Not copying the current list before adding. result.add(current) adds a reference that gets modified by backtracking. Always add a copy.
• Missing the base case when start == s.length(). Without it, you recurse forever past the end of the string.

Frequently Asked Questions

Is every string guaranteed to have at least one valid partition? Yes. Any string can be partitioned into individual characters, and every single character is a palindrome.

How do you optimize the palindrome check? Precompute a boolean 2D table where dp[i][j] is true if s[i..j] is a palindrome. Fill it in O(n^2) before backtracking, then each check is O(1). This is worth doing when n is large.

Can this be solved with DP alone (without backtracking)? If you only need the minimum number of cuts (Palindrome Partitioning II), yes. If you need all actual partitions, backtracking is required.

← All Problems