Palindrome Partitioning

NeetCode: Palindrome Partitioning · LeetCode: 131. Palindrome Partitioning · Difficulty: Medium

Given a string s, partition it so that every substring of the partition is a palindrome, and return all possible partitions.

Example

Text

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

Brute force: backtrack and test each piece

At position start, try every end end >= start. If s[start..end] (both ends included) is a palindrome, take it as the next piece, recurse from end + 1, then undo. When start reaches the end of the string, the pieces form a complete partition. Each palindrome check is a two-pointer scan, and the same substring is re-checked in many branches of the recursion.

LeetCode's Java signature returns List<List<String>>. s.substring(start, end + 1) takes the piece (its end index is exclusive), and the leaf stores a copy of the shared current list. charAt reads a 16-bit char, which is enough for the lowercase letters in the constraints.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class Solution {
        public List<List<String>> partition(String s) {
            List<List<String>> result = new ArrayList<>();
            dfs(0, s, new ArrayList<>(), result);
            return result;
        }

        private boolean isPal(String s, int lo, int hi) {
            int i = lo, j = hi;
            while (i < j) {
                if (s.charAt(i) != s.charAt(j)) {
                    return false;
                }
                i++;
                j--;
            }
            return true;
        }

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

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

Output

[[a, a, b], [aa, b]]
[[a]]

Time: O(n² · 2^n) as an upper bound (up to 2^n partitions, and palindrome checks of up to n characters along the way). Space: O(n) recursion depth besides the output.

Optimal: precompute a palindrome table

A substring s[i..j] is a palindrome exactly when s[i] == s[j] and the inside s[i+1..j-1] is a palindrome (or is empty or a single character). This is a small DP: fill pal[i][j] for i from the end of the string down to 0, so pal[i+1][j-1] is always ready. Building the table costs O(n²) once, and every palindrome test in the backtracking is then a single lookup. A boolean[n][n] array starts filled with false.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class Solution {
        public List<List<String>> partition(String s) {
            int n = s.length();
            boolean[][] pal = new boolean[n][n];
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i; j < n; j++) {
                    pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
                }
            }
            List<List<String>> result = new ArrayList<>();
            dfs(0, s, pal, new ArrayList<>(), result);
            return result;
        }

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

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

Output

[[a, a, b], [aa, b]]
[[a]]

Time: O(n²) for the table plus O(n · 2^n) for the search (each partition is copied, and the worst case is a string like "aaaa" where all 2^(n-1) partitions are valid). Space: O(n²) for the table plus recursion depth O(n).