Crack the Backend

Problem Statement

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible partitionings. A palindrome reads the same forward and backward. Each partitioning is a list of strings (substrings of s) whose concatenation equals s.

We build a partition from left to right. At position start, we try every possible end end (start to n-1); if s[start..end] is a palindrome, we add it to the current path and recurse on start = end+1. When start == s.length(), we have partitioned the whole string — add the path to the result.

Key Observations

Backtracking: dfs(start, path): if start == s.length(), add a copy of path to the result. Otherwise, for end = start..n-1, if s.substring(start, end+1) is a palindrome, path.add that substring, dfs(end+1, path), path.remove (backtrack).
To check palindrome in O(length): two pointers or compare with reversed substring. We can also precompute a isPal[i][j] table.

Approach

High-level: DFS(start): if start==n add path. For end=start..n-1: if s[start..end] is palindrome, path.add(substring), dfs(end+1), path.remove.

Steps: dfs(start): if start==s.length() add new ArrayList(path). For end=start to n-1: if isPalindrome(s, start, end), path.add(s.substring(start, end+1)), dfs(end+1), path.remove(path.size()-1).

Implementation

Java

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

void dfs(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 (isPal(s, start, end)) {
            path.add(s.substring(start, end + 1));
            dfs(s, end + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

boolean isPal(String s, int i, int j) {

    while (i < j) {
        if (s.charAt(i++) != s.charAt(j--)) {
            return false;
        }
    }

    return true;
}

Test Cases

Example 1

Input

s = "aab"

Expected

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

Explanation

Two partitionings.

Complexity Analysis

Time: O(n * 2^n).
Space: O(n).

Follow-ups

Palindrome Partitioning II: minimum cuts (DP).