Palindrome Partitioning

Problem Link

Palindrome Partitioning – LeetCode

Problem: Palindrome Partitioning

Problem Statement

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

Examples

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

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

Constraints

• 1 <= s.length <= 16

• s contains only lowercase English letters.

Intuition

We need to try all ways to partition the string and only keep those where every substring is a palindrome.

This is a perfect candidate for backtracking:

• At every index, try all possible substrings.

• If the current substring is a palindrome, make a recursive call from the next index.

• When the entire string is consumed, add the current partition to the result.

Approach (Backtracking – Input-Output Method)

1. Use a recursive helper function that takes:

   • The current index sidx

   • A list path of palindromic substrings found so far

   • The final answer list ans

2. At each step, try all substrings from sidx to end:

   • If a substring s[sidx...end] is a palindrome:

     • Add it to the current path

     • Recurse from end+1

     • Backtrack after recursion

3. The base case is when sidx == s.length():

   • Add the current path as a valid partition.

Code (Java)

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

    private void helper(String s, int sidx, List<String> path, List<List<String>> ans) {
        if (sidx == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int end = sidx + 1; end <= s.length(); end++) {
            if (isPalindrome(s, sidx, end - 1)) {
                path.add(s.substring(sidx, end));
                helper(s, end, path, ans);
                path.remove(path.size() - 1); // backtrack
            }
        }
    }

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

Time and Space Complexity

• Time Complexity: O(2^n * n)

  • Each character may be partitioned or not (2^n combinations).

  • For each combination, we check palindromes in O(n).

• Space Complexity: O(n) recursion stack + result storage.

Dry Run

Input: s = "aab"

Recursive Tree:

helper(0, [])
├── Try "a" → palindrome
│   └── helper(1, ["a"])
│       ├── Try "a" → palindrome
│       │   └── helper(2, ["a", "a"])
│       │       ├── Try "b" → palindrome
│       │       │   └── helper(3, ["a", "a", "b"]) → ans.add(["a","a","b"])
│       └── Try "ab" → not palindrome
├── Try "aa" → palindrome
│   └── helper(2, ["aa"])
│       └── Try "b" → palindrome
│           └── helper(3, ["aa", "b"]) → ans.add(["aa", "b"])
├── Try "aab" → not palindrome

Final Answer: [["a","a","b"], ["aa","b"]]

Conclusion

This is a classic backtracking problem where you:

• Explore all possible partitions.

• Prune paths where a substring is not a palindrome.

• Use recursion and backtracking to build valid partitions.

This reinforces the input-output recursion concept with pruning based on problem-specific constraints.