Palindrome Partitioning

MediumBacktrackingbacktracking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given a string s, split it into one or more contiguous pieces so that **every** piece reads the same forwards and backwards (a palindrome). Return **all** the distinct ways to partition s under this rule. Each way is a list of the pieces in left-to-right order, and concatenating those pieces must reproduce s exactly. A single character counts as a palindrome, so the trivial split into individual characters is always one valid partition. The order in which you return the partitions does not matter, and the pieces within a single partition must stay in their original order.

Examples

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Splitting after every character gives `["a","a","b"]`. Grouping the first two characters gives `["aa","b"]`. Both pieces in each partition are palindromes.
Input: s = "a"
Output: [["a"]]
A single character is already a palindrome, so the only partition is the string itself.
Input: s = "aba"
Output: [["a","b","a"],["aba"]]
Either split into three single characters, or keep the whole string since `"aba"` is a palindrome.

Constraints

  • `1 <= s.length <= 16`
  • `s` consists only of lowercase English letters.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More backtracking problems