131. Palindrome Partitioning
You are given a lowercase string s. Cut it into a sequence of contiguous, non-empty pieces so that every piece reads the same forwards and backwards, and return all such partitions.
Because single characters are palindromes, at least one partition always exists (cut between every pair of letters).
To keep the answer canonical, list partitions in search order: build each partition left to right, always trying the next piece from shortest to longest before moving on. (This is exactly the order a depth-first backtracking search produces when it extends the current piece one character at a time.)
Example 1:
Input: s = "aab"
Output: [["a","a","b"], ["aa","b"]]
Explanation: Both cuts of "aab" into palindromic pieces: ["a","a","b"] comes first because its first piece "a" is shorter than "aa".
Example 2:
Input: s = "efe"
Output: [["e","f","e"], ["efe"]]
Explanation: "efe" splits into three single letters, or stays whole since it is itself a palindrome.
Example 3:
Input: s = "ab"
Output: [["a","b"]]
Explanation: Neither "ab" nor any multi-letter piece of it is a palindrome, so the only option is single letters.
Constraints:
- 1 ≤ s.length ≤ 16
- s consists of lowercase English letters.
Hints:
A partition is determined by where its first piece ends. Once you fix a palindromic prefix, the rest of the job is the identical problem on the remaining suffix — that recursive shape is the whole solution.
Backtrack: at position start, try every end where s[start..end] is a palindrome, append that piece, recurse from end + 1, then pop it off. Trying end in increasing order yields exactly the required canonical order.
Each palindrome check costs O(piece length) if done by two pointers. Precompute a table pal[i][j] = (s[i] == s[j] and pal[i+1][j-1]) so every check during the search is O(1).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "aab"
Expected output: [["a","a","b"], ["aa","b"]]