MediumBacktracking
Palindrome Partitioning
amazongooglemetabloombergmicrosoftuber
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s.
Examples
Example 1
Input
s = "aab"
Output
[["a","a","b"],["aa","b"]]
"a", "a", "b" are all palindromes. "aa" and "b" are also both palindromes.
Example 2
Input
s = "a"
Output
[["a"]]
A single character string has only one partition, and it is a palindrome.
Example 3
Input
s = "aba"
Output
[["a","b","a"],["aba"]]
Both individual characters and the full string "aba" are palindromes.
Constraints
- 1 <= s.length <= 16
- s contains only lowercase English letters
Optimal complexity
Time
O(n * 2^n)
Space
O(n)
One problem, two ways to prep
Choose between solo practice and interview simulation
Practice Mode keeps things simple with code + tests. AI Interview Mode adds voice, pressure, and a post-round score summary.