Palindrome Partitioning — Medium Coding Interview Question

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example

Input: s = "aab"

Output: [["a","a","b"],["aa","b"]]

Constraints

• 1 ≤ s.length ≤ 16
• s contains only lowercase English letters

Topics & Companies

Topics: backtracking, dp

Asked by: Amazon, Google, Meta, Microsoft, Bloomberg

Optimal Solution Complexity

Time complexity: O(n × 2^n). Space complexity: O(n²).

Practice more

• All DSA Problems
• DSA Patterns