Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s.
Example 1:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Explanation: Both ["a","a","b"] and ["aa","b"] are valid partitions where every part is a palindrome.
Example 2:
Input: s = "a"
Output: [["a"]]
Explanation: A single character is always a palindrome.
Examples
Example 1
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Explanation: "a", "a", "b" are all palindromes. "aa" and "b" are also both palindromes.
Example 2
Input: s = "a"
Output: [["a"]]
Explanation: A single character string has only one partition, and it is a palindrome.
Example 3
Input: s = "aba"
Output: [["a","b","a"],["aba"]]
Explanation: 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)
Practice this problem with an AI interviewer
TechInView conducts a full voice mock interview — the AI asks clarifying questions, evaluates your approach, watches you code, and scores you on 5 dimensions. Just like a real FAANG interview.
Start a free interview