MediumBacktrackingAI interview only
Palindrome Partitioning
Asked atamazongooglemetabloombergmicrosoftuber
01 · Problem
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s.
02 · Examples
Example 01
Input
s = "aab"
Output
[["a","a","b"],["aa","b"]]
"a", "a", "b" are all palindromes. "aa" and "b" are also both palindromes.
Example 02
Input
s = "a"
Output
[["a"]]
A single character string has only one partition, and it is a palindrome.
Example 03
Input
s = "aba"
Output
[["a","b","a"],["aba"]]
Both individual characters and the full string "aba" are palindromes.
03 · Constraints
- 011 <= s.length <= 16
- 02s contains only lowercase English letters
04 · Optimal complexity
- Time
- O(n * 2^n)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.