LeetCode Problem 131

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Backtracking

Solution

LeetCode 131, Palindrome Partitioning

Problem Understanding

The problem gives us a string s and asks us to divide it into substrings such that every substring is a palindrome. A palindrome is a string that reads the same forward and backward. We must return all possible valid ways to partition the string.

A partition means splitting the string into contiguous pieces. Every character in the original string must belong to exactly one substring in the partition, and the substrings must appear in the original order.

For example, if the input is "aab", there are two valid palindrome partitions:

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

The first partition works because every individual character is a palindrome. The second works because "aa" is also a palindrome.

The input size is relatively small, with s.length <= 16. This is an important clue. Problems involving "return all possible combinations" often have exponential output sizes, and a small constraint usually indicates that exponential exploration is acceptable.

The challenge is not only finding palindromes, but efficiently exploring every possible partition while avoiding unnecessary repeated work.

Several edge cases are important:

• A single-character string is always a palindrome, so the answer is simply [[s]].
• A string where every character is the same, like "aaaa", creates many valid partitions.
• A string with no multi-character palindromes, like "abc", only allows partitions of single characters.
• Since the problem guarantees lowercase English letters and a minimum length of 1, we do not need to handle empty input or invalid characters.

Approaches

Brute Force Approach

The brute force solution tries every possible way to split the string, then checks whether every substring in that partition is a palindrome.

For a string of length n, there are n - 1 possible split positions. Each position can either contain a cut or not contain a cut, which means there are 2^(n-1) possible partitions.

For each partition, we must validate every substring by checking whether it is a palindrome. A palindrome check takes O(k) time for substring length k.

This approach is correct because it exhaustively explores every partition configuration. However, it performs a large number of repeated palindrome checks. The same substring may be tested many times across different recursive branches.

Because of this redundancy, the brute force method becomes inefficient.

Optimal Approach

The key insight is that the problem naturally forms a decision tree.

At every index, we can choose any palindrome substring starting at that position, then recursively solve the remaining suffix of the string.

Instead of generating every partition first and validating later, we only build valid partitions from the beginning.

We can further optimize the solution by precomputing whether every substring s[i:j] is a palindrome using dynamic programming.

This preprocessing allows palindrome checks in O(1) time during backtracking.

The algorithm therefore combines:

• Dynamic programming for fast palindrome lookup
• Backtracking for generating all valid partitions

This is much more efficient because we avoid repeated palindrome computations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × 2^n × n)	O(n × 2^n)	Generates all partitions and repeatedly checks palindromes
Optimal	O(n^2 + n × 2^n)	O(n^2 + n × 2^n)	Uses DP preprocessing with backtracking

Algorithm Walkthrough

Step 1: Precompute palindrome substrings

Create a 2D table is_palindrome where:

is_palindrome[i][j] = True

if the substring s[i:j+1] is a palindrome.

We fill this table from shorter substrings to longer substrings.

A substring is a palindrome if:

• The characters at both ends match
• The inner substring is also a palindrome

Formally:

s[i] == s[j] and is_palindrome[i+1][j-1]

For substrings of length 1 or 2, matching ends are sufficient.

Step 2: Start backtracking from index 0

We recursively build partitions starting from the beginning of the string.

At each position start, we try every possible ending index end.

If s[start:end+1] is a palindrome, we:

1. Add it to the current partition
2. Recursively continue from end + 1
3. Remove the substring afterward to backtrack

Step 3: Record completed partitions

If start == len(s), we have consumed the entire string.

At this point, the current partition contains only palindrome substrings and represents a valid solution.

We add a copy of the partition to the result list.

Step 4: Continue exploring all possibilities

Backtracking ensures we systematically explore every valid partition configuration.

Because we only recurse on palindrome substrings, every generated partition is automatically valid.

Why it works

The algorithm maintains the invariant that every substring currently stored in the partition is a palindrome.

At each recursive step, we extend the partition only with valid palindrome substrings. Since every possible palindrome extension is explored, no valid partition is missed.

The recursion terminates only when the entire string has been partitioned, guaranteeing that every recorded result is complete and correct.

Python Solution

from typing import List

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)

        # Precompute palindrome table
        is_palindrome = [[False] * n for _ in range(n)]

        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j]:
                    if j - i <= 2 or is_palindrome[i + 1][j - 1]:
                        is_palindrome[i][j] = True

        result = []
        current_partition = []

        def backtrack(start: int) -> None:
            if start == n:
                result.append(current_partition[:])
                return

            for end in range(start, n):
                if is_palindrome[start][end]:
                    current_partition.append(s[start:end + 1])

                    backtrack(end + 1)

                    current_partition.pop()

        backtrack(0)

        return result

The implementation begins by building the is_palindrome table. The nested loops iterate from right to left for the starting index so that smaller substrings are already computed before larger ones depend on them.

The condition:

j - i <= 2

handles substrings of length 1, 2, and 3. These cases do not require checking an inner substring.

After preprocessing, the solution uses recursive backtracking.

The current_partition list stores the substrings chosen so far. Whenever we find a palindrome substring, we append it and recursively continue searching from the next position.

Once recursion returns, we remove the substring using pop(). This restores the previous state so other choices can be explored.

The line:

result.append(current_partition[:])

creates a copy of the current partition. Without copying, later modifications would affect previously stored results.

Go Solution

func partition(s string) [][]string {
	n := len(s)

	isPalindrome := make([][]bool, n)
	for i := range isPalindrome {
		isPalindrome[i] = make([]bool, n)
	}

	// Precompute palindrome table
	for i := n - 1; i >= 0; i-- {
		for j := i; j < n; j++ {
			if s[i] == s[j] {
				if j-i <= 2 || isPalindrome[i+1][j-1] {
					isPalindrome[i][j] = true
				}
			}
		}
	}

	var result [][]string
	var current []string

	var backtrack func(start int)

	backtrack = func(start int) {
		if start == n {
			partitionCopy := make([]string, len(current))
			copy(partitionCopy, current)

			result = append(result, partitionCopy)
			return
		}

		for end := start; end < n; end++ {
			if isPalindrome[start][end] {
				current = append(current, s[start:end+1])

				backtrack(end + 1)

				current = current[:len(current)-1]
			}
		}
	}

	backtrack(0)

	return result
}

The Go implementation follows the same algorithmic structure as the Python version.

One important difference is slice copying. In Go, slices reference shared underlying arrays, so we must explicitly create a new slice before appending it to the result:

partitionCopy := make([]string, len(current))
copy(partitionCopy, current)

Without this copy, later modifications to current would affect stored results.

Another difference is slice backtracking:

current = current[:len(current)-1]

This removes the most recently added substring.

Worked Examples

Example 1

Input:

s = "aab"

Palindrome Table

Substring	Palindrome
"a"	True
"a"	True
"b"	True
"aa"	True
"ab"	False
"aab"	False

Backtracking Trace

Step	Current Index	Current Partition	Action
1	0	[]	Start recursion
2	0	["a"]	Choose "a"
3	1	["a", "a"]	Choose second "a"
4	2	["a", "a", "b"]	Choose "b"
5	3	["a", "a", "b"]	Reached end, save result
6	1	["aa"]	Backtrack, choose "aa"
7	2	["aa", "b"]	Choose "b"
8	3	["aa", "b"]	Reached end, save result

Final result:

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

Example 2

Input:

s = "a"

Palindrome Table

Substring	Palindrome
"a"	True

Backtracking Trace

Step	Current Index	Current Partition	Action
1	0	[]	Start recursion
2	1	["a"]	Reached end, save result

Final result:

[
    ["a"]
]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2 + n × 2^n)	DP preprocessing takes O(n^2), backtracking explores exponential partitions
Space	O(n^2 + n × 2^n)	DP table plus recursion and output storage

The dynamic programming preprocessing requires an n × n table.

The backtracking phase can generate exponentially many valid partitions in the worst case, especially for strings like "aaaaaa" where nearly every substring is a palindrome.

Since the problem requires returning all partitions, the output size itself can be exponential, making this complexity unavoidable.

Test Cases

from typing import List

def normalize(result: List[List[str]]) -> List[List[str]]:
    return sorted(sorted(partition) for partition in result)

solution = Solution()

# Example case
assert normalize(solution.partition("aab")) == normalize([
    ["a", "a", "b"],
    ["aa", "b"]
])  # standard example with multiple valid partitions

# Single character
assert solution.partition("a") == [["a"]]  # smallest valid input

# No multi-character palindromes
assert normalize(solution.partition("abc")) == normalize([
    ["a", "b", "c"]
])  # only single-character partitions possible

# Entire string is palindrome
assert normalize(solution.partition("aba")) == normalize([
    ["a", "b", "a"],
    ["aba"]
])  # includes whole-string palindrome

# All characters identical
assert normalize(solution.partition("aaa")) == normalize([
    ["a", "a", "a"],
    ["a", "aa"],
    ["aa", "a"],
    ["aaa"]
])  # many overlapping palindrome choices

# Even-length palindrome
assert normalize(solution.partition("abba")) == normalize([
    ["a", "b", "b", "a"],
    ["a", "bb", "a"],
    ["abba"]
])  # tests even-length palindromes

# Complex overlapping palindromes
assert normalize(solution.partition("racecar")) == normalize([
    ["r", "a", "c", "e", "c", "a", "r"],
    ["r", "a", "cec", "a", "r"],
    ["r", "aceca", "r"],
    ["racecar"]
])  # nested palindrome structures

Test	Why
"aab"	Standard example with multiple answers
"a"	Minimum input size
"abc"	No multi-character palindromes
"aba"	Odd-length palindrome
"aaa"	Large branching factor
"abba"	Even-length palindrome
"racecar"	Deeply nested palindromes

Edge Cases

Single Character Input

A string of length 1 is always a palindrome. This case is important because recursive algorithms sometimes mishandle minimal input sizes or produce empty partitions accidentally.

The implementation handles this naturally. The palindrome table marks the single character as valid, and the recursion immediately reaches the base case after choosing it.

Strings Without Multi-Character Palindromes

Inputs like "abc" can expose bugs where the algorithm incorrectly assumes larger palindromes exist.

In this situation, only single-character substrings are valid. The algorithm still works because every single character satisfies the palindrome condition, allowing recursion to progress one character at a time.

Strings With Many Overlapping Palindromes

Inputs like "aaaa" generate a very large number of valid partitions because almost every substring is a palindrome.

This is challenging because inefficient palindrome checking would repeatedly recompute the same information.

The DP preprocessing solves this problem efficiently by storing palindrome results once and reusing them throughout the recursion.

Even-Length Palindromes

Some implementations accidentally only handle odd-length palindromes correctly.

For example, "abba" contains "bb" and "abba" as even-length palindromes.

The condition:

j - i <= 2

combined with matching boundary characters correctly handles both even-length and odd-length palindrome cases.