Algorithm Day62 - Palindrome Partitioning

Posted on In , Views:

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

💬 Example

Example 1

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

Example 2

1
2
Input: s = "a"
Output: [["a"]]

💡 Intuition

We need to explore all possible partitions of the string and check if each substring is a palindrome.

This is a classic backtracking problem:

  1. Start from index 0.
  2. Expand substring [start..i].
  3. If it is a palindrome, recursively partition the rest.
  4. Collect valid partitions when we reach the end.

🔢 Java Code (Backtracking)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;

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

    private void backtrack(List<List<String>> res, List<String> path, String s, int start) {
        if (start == s.length()) {
            res.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(res, path, s, end + 1);
                path.remove(path.size() - 1);
            }
        }
    }

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

⏱ Complexity Analysis

Let n = s.length().

  • Time: O(n × 2^n) — because each index can start a new partition cut, and palindrome check takes O(n).
  • Space: O(n) recursion depth + O(n) for substring storage.

✍️ Summary

  • Use backtracking to explore all partitions.
  • Only continue recursion if substring is a palindrome.
  • Collect valid partitions when reaching the end.

Related problems

  • lc-132 — Palindrome Partitioning II (min cuts)
  • lc-647 — Palindromic Substrings
  • lc-5 — Longest Palindromic Substring