Backtracking · 126Medium
Palindrome Partitioning
Given a string s, partition it so every substring in the partition is a palindrome. Return all possible palindrome partitionings.
Constraints
- 1 <= s.length <= 16
- s contains only lowercase English letters.
Examples
partition("aab") -> [["a","a","b"], ["aa","b"]]
partition("a") -> [["a"]]
partition("ab") -> [["a","b"]] // no multi-character palindrome
partition("aa") -> [["a","a"], ["aa"]]
partition("aba") -> [["a","b","a"], ["aba"]]
partition("aaa") -> [["a","a","a"], ["a","aa"], ["aa","a"], ["aaa"]]Edge cases
- Single characters are always palindromes, so a partitioning always exists.
- Cuts must cover the whole string with no gaps.
Show the target complexity (spoiler)
- Naive
- O(n * 2^n) time — generate every partitioning and validate each part afterwards.
- Target
- Backtracking that only recurses when the current prefix is already a palindrome, optionally with an O(n^2) precomputed palindrome table.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/10-backtracking/126-palindrome-partitioning.js ./practice c 126