Palindrome Partitioning

Palindrome partitioning asks for every way to cut a string into contiguous pieces where each piece is a palindrome — a run of characters that reads the same forwards and backwards, like aa, b, or racecar. This is LeetCode 131. For aab there are exactly two such splits: a | a | b and aa | b. You return them as a list of partitions, where each partition is an array of its pieces in left-to-right order.

Signature

palindromePartitioning(s)  // string -> array of partitions (each partition an array of palindrome pieces)

Examples

palindromePartitioning('aab');
// [['a', 'a', 'b'], ['aa', 'b']]

palindromePartitioning('a');
// [['a']]

palindromePartitioning('aba');
// [['a', 'b', 'a'], ['aba']]

Notes

• Every piece is a palindrome — a single character always reads the same both ways, so a partition always exists; in the worst case you cut every character apart.
• Pieces cover the whole string — concatenating a partition's pieces in order reproduces s exactly, with nothing dropped, added, or reordered.
• Order is not specified — return the partitions (and find the pieces within each) in any order; only the collection of partitions matters, not its arrangement.
• Empty string — palindromePartitioning('') returns [[]]: a single partition that contains no pieces.
• Build it yourself — no libraries; the whole point is the search over cut positions.