PPractick

The problem

A word-game app awards bonus points when a word can be cut into pieces that are all palindromes (read the same both ways). For a given word, the app wants every way to cut it so that each piece is a palindrome. For "aab", that's a | a | b and aa | b. Backtracking tries every possible first piece, keeps only palindromic ones, and recursively partitions the rest of the string.

Example: "aab" → [a,a,b], [aa,b].

Function signature

vector<vector<string>> partition(const string& s);

Test cases

Input	Output	Explanation
"aab"	[a,a,b] [aa,b]
"a"	[a]
"aba"	[a,b,a] [aba]
"abba"	[a,b,b,a] [a,bb,a] [abba]
"ab"	[a,b]	Single letters are always palindromes

(Confirm: every piece must be a non-empty palindrome; the pieces must cover the whole string in order; n is at most 16.)

How interviewers phrase it

• "Partition s such that every substring of the partition is a palindrome; return all possible partitions" (LeetCode 131).
• A harder follow-up asks for the minimum number of cuts (LeetCode 132, DP).

Clarifying questions to ask

1. Return all partitions, or only the count or minimum cuts?
2. How long can s be? (Up to 16, since the output can be exponential.)
3. Are single characters valid pieces? (Yes, always.)

Follow-ups to expect

1. "How many partitions can there be?"
2. "How do you speed up the palindrome checks?"
3. "What's the recursion structure?"
4. "How would you find the minimum number of cuts?"
5. "Complexity?"

Related questions

• Letter Combinations of a Phone Number Hard
• Expression Add Operators Hard
• Word Search Hard
• N Queen Hard
• Rat in a Maze Hard
• M Coloring Problem Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in