Palindrome Partitioning

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

Backtracking LeetCode 131 ↗ Medium

Problem

Input: A string s

Output: All possible palindrome partitionings

Example:

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

Constraints:

1 ≤ s.length ≤ 16
s contains only lowercase English letters

Interactive Visualization

String:

Presets:

Speed: 800ms

String & Current Partition

Palindrome Check: -

Current Partition

Empty

Valid Partitions Found: 0

Code

fun partition(s: String): List<List<String>> {    val result = mutableListOf<List<String>>()    fun isPalindrome(sub: String): Boolean {        return sub == sub.reversed() }    fun backtrack(start: Int, current: MutableList<String>) {        if (start == s.length) {            result.add(ArrayList(current))            return }        for (end in start + 1..s.length) {            val substring = s.substring(start, end)            if (isPalindrome(substring)) {                current.add(substring)                backtrack(end, current)                current.removeAt(current.size - 1)    }   }   }    backtrack(0, mutableListOf())    return result }

def partition(s):    result = []        def is_palindrome(sub):        return sub == sub[::-1]        def backtrack(start, current):        if start == len(s):            result.append(current[:])            return                for end in range(start + 1, len(s) + 1):            substring = s[start:end]            if is_palindrome(substring):                current.append(substring)                backtrack(end, current)                current.pop()        backtrack(0, [])    return result

Status

Ready to start

How It Works

Key Insight

Use backtracking to explore all possible ways to partition the string. At each position, try all possible substrings starting from that position. If a substring is a palindrome, add it to the current partition and recursively partition the remaining string.

Algorithm Steps

Initialize: Create an empty result list and start backtracking from position 0 with an empty partition
Base Case: If we've reached the end of the string, we have a valid partition - add it to results
Try All Splits: For each possible end position from current start, extract substring
Check Palindrome: If substring is a palindrome, add it to current partition
Recurse: Continue partitioning from the end position with updated partition
Backtrack: Remove the last added substring and try the next possibility
Return: All collected valid partitions

Complexity Analysis

Metric	Complexity	Explanation
Time	`O(n·2^n)`	In worst case, we have 2^n possible partitions and checking each partition takes O(n) time
Space	`O(n)`	Recursion stack depth is at most n (length of string)