A palindrome reads the same forwards and backwards, like "kayak" or "z". Cut the string s into consecutive, non-empty pieces so that every piece is a palindrome, and return every way of doing it.
Each way is a list of its pieces in the order they appear in s, so joining them gives back s. A single letter is always a palindrome, so cutting between every pair of letters always works. You may list the ways in any order, but the pieces inside each one must stay in string order.
Besides cutting into single letters, the middle "oo" can stay together, and so can the whole word. Pieces like "no" or "noo" aren't palindromes, so no other cut works.
The as can be split or joined, and so can the bs, independently: 2 × 2 = 4 ways.
No two neighbouring letters match, so single letters are the only way.
Constraints
1 <= s.length <= 16s contains only lowercase English letters.Choose the first piece, then partition what is left the same way: from position start, try every palindrome s[start..end] and recurse on end + 1 (backtracking). Reaching the end of the string completes one partition.